Создать коммутативный хеш на основе трех наборов чисел?

Question

Мне нужно сгенерировать коммутативный хеш, основанный на трех наборах структур "Score".

Каждый счет имеет «начало», «конец» и «число».

И начало, и конец, как правило, огромные числа (8-9 цифр), но число от 1 до 4.

Мне нужно, чтобы они были коммутативными, поэтому порядок не имеет значения. Сейчас я использую XOR, но, похоже, он дает плохие результаты.

Поскольку я работаю с большими большими наборами данных, я бы предпочел решение, дружественное к производительности. Какие-либо предложения? Спасибо =]

    public static int getCustomHash(cnvRegion c1, cnvRegion c2, cnvRegion c3)
    {
        int part1 = (c1.startLocation * c2.startLocation * c3.startLocation);
        int part2 = (c1.endLocation * c2.endLocation * c3.endLocation);
        int part3 = (c1.copyNumber + c2.copyNumber + c3.copyNumber)*23735160;
        return part1 ^ part2 ^ part3;
    }

Answer 1

Во-первых, я думаю, что требования не совсем ясны. Если вы хэшируете три набора данных c1, c2 и c3. Затем, если вы переключитесь, c1.copyNumber и c2.copyNumber и снова хешируйте. Должен ли это дать тот же результат или нет? Если вы переключите c1.startLocation с c1.endLocation. Должно ли это привести к тому же хешу или нет?

Я собираюсь предположить, что вы хотели бы иметь разные результаты хеширования в обоих случаях и что единственная перестановка, которая не должна изменять результат хеширования, это перестановки наборов данных c1, c2, c3.

Если это так, то я бы предложил сначала хэшировать три набора данных независимо от меньших значений. То есть h1 = H (c1) h2 = H (c2) h3 = H (c3) где H может быть любой хеш-функцией (например, CRC32, Adler32, SHA1 и т. д.), в зависимости от того, как сильно вы хотите избежать коллизий.

Следующим шагом будет вычисление коммутативного хеша h1, h2, h3. Если вы хотите избежать коллизий, если только h1, h2, h3 не переставлены, тогда работает следующее. Вычислить полином

• P (x) = (x-h1) (x-h2) (x-h3)

затем хеширует полином (rsp. Его коэффициенты) с любой хорошей хеш-функцией. То есть тот будет

• H (h1 + h2 + h3 || h1 * h2 + h1 * h3 + h2 * h3 || h1 * h2 * h3), где || это конкатенация.

Если вы хотите избежать любой ненужной коллизии любой ценой, то коэффициенты должны быть вычислены как целые числа с множественной точностью, и должна использоваться хеш-функция, устойчивая к коллизиям, такая как SHA1. Из-за уникального факторизационного свойства многочленов следует, что коэффициенты многочлена различны, если h1, h2 и h3 различны. Но кажется, что избегать столкновений любой ценой в вашем случае - излишне.

Таким образом, вместо того, чтобы вычислять полином P (x) символически, можно просто оценить его по произвольному значению R. I.e. если h1, h2, h3 являются просто 32-битными значениями, тогда вычисляется следующее может быть достаточно: (какой-то псевдокод типа C следует. Я не знаю, что C # использует для 64-битных целых чисел)

const long long R = SOME_RANDOM_64_BIT_CONSTANT;
long long hash0 = (R - h1) * (R - h2) * (R - h3);
int hash = (int) (hash0 >> 32);

Я здесь использую 64-битное умножение, потому что они достаточно быстрые на современных процессорах, и я использую верхний 32-битный хэш-код, а не 32-битный, потому что младшие 32-битные смещены. Т.е. младший значащий бит с большей вероятностью будет равен 0, чем 1.

Answer 2

Томас Ванг обсуждает хеш-функции здесь .

• См. Метод Кнута и функции микширования от 64 до 32 бит.

У Пола Се также есть страница о целочисленном хешировании, , которая описывает его функцию "SuperFastHash", получившую смешанную обратную связь.

EDIT

Поскольку вы хотите, чтобы ваш пользовательский хэш был коммутативным (я полагаю, между параметрами cnvRegion), вы, вероятно, могли бы написать что-то вроде этого:

public int hash6432shift(long key)
{
   key = (~key) + (key << 18); // key = (key << 18) - key - 1;
   key = key ^ (key >>> 31);
   key = key * 21; // key = (key + (key << 2)) + (key << 4);
   key = key ^ (key >>> 11);
   key = key + (key << 6);
   key = key ^ (key >>> 22);
   return (int) key;
}

public static int getCustomHash(cnvRegion c1, cnvRegion c2, cnvRegion c3)
{
    int part1 = (c1.startLocation ^ c2.startLocation ^ c3.startLocation);
    int part2 = (c1.endLocation ^ c2.endLocation ^ c3.endLocation);
    int part3 = (c1.copyNumber ^ c2.copyNumber ^ c3.copyNumber);

    int hash1 = hash6432shift(((long)part1 << 0x20) | part2);
    return hash6432shift(((long)hash1 << 0x20) | part3);
}

Однако, в конце концов, задача нахождения хеш-функции, которая одновременно быстра и обеспечивает хорошее сопротивление столкновению, очень зависит от данных, которые вы обрабатываете.

Позвольте привести пример:

Предположим, что значения, которые вы хэшируете, являются большими, 10-значными числами, и они представляют метку времени UNIX (время, прошедшее в секундах с 01.01.1970). В этом случае хэширование большого количества временных меток, которые происходят в течение ограниченного промежутка времени, скажем, более месяца, это просто вопрос удаления части, которая не изменяется, и использования только той части метки времени, которая сильно изменяется. Это то же самое, что сказать, что вы удаляете части с низкой энтропией.

v1 = 1241536920   // 5/5/2009 3:22:00 PM
v2 = 1241529720   // 5/5/2009 1:22:00 PM
v3 = 1241270520   // 5/2/2009 1:22:00 PM
v4 = 1242825720   // 5/20/2009 1:22:00 PM

Совершенно очевидно, что мы могли бы безопасно удалить первые 3-4 цифры и использовать только оставшиеся цифры в качестве хеша. Кроме того, если эти значения обычно появляются в течение нескольких минут друг от друга, вы также можете сбросить последние 2-3 цифры.

Таким образом, у вас осталось только 4 цифры, которые вы можете использовать в качестве хеша с довольно хорошим сопротивлением столкновению для нашего примера.

Моя точка зрения такова, что хеш-функции могут быть высоко оптимизированы, если вы знаете статистическое распределение значений, которые вы пытаетесь хэшировать.