Строка в целочисленную функцию хеширования с точностью

Question

Я хочу хэшировать массив символов в int или long. Результирующее значение должно соответствовать заданному значению точности. Функция, которую я использовал, приведена ниже:

int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}

Строка для хэширования аналогична "SAEUI1210.00000010_1".

Однако в некоторых случаях это приводит к дублированию значений. Есть ли хорошие альтернативы, которые бы не дублировали один и тот же хеш для разных строковых значений.

Answer 1

Само определение хеша состоит в том, что он создает повторяющиеся значения для некоторых значений, поскольку диапазон значений хеша меньше, чем пространство хешированных данных.

Теоретически, 32-битный хэш имеет достаточный диапазон, чтобы хэшировать все ~ 6 символьных строк (A-Z, a-z, только 0-9), не вызывая коллизии. На практике хеши не являются идеальной перестановкой входных данных. Учитывая 32-битный хеш, вы можете ожидать получения хеш-коллизий после хэширования ~ 16 битных случайных входов, из-за парадокса дня рождения .

Учитывая статический набор значений данных, всегда можно создать специально созданную для них хеш-функцию, которая никогда не будет конфликтовать с самим собой (разумеется, размер ее вывода будет не менее log(|data set|). Однако для этого требуется чтобы вы знали все возможные значения данных заранее, это называется идеальное хеширование .

При этом, здесь - это несколько альтернатив, которые должны помочь вам начать (они предназначены для минимизации столкновений)

Answer 2

Хеши генерируют одно и то же значение для разных входных данных - это то, что они делают. Все, что вы можете сделать, это создать хеш-функцию с достаточным распределением или битовой глубиной (или обеими), чтобы минимизировать эти конфликты. Поскольку у вас есть это дополнительное ограничение точности (0-5?), Вы будете сталкиваться с столкновениями гораздо чаще.

Answer 3

У каждого хэша будут коллизии. Период. Это называется проблема дня рождения .

Возможно, вы захотите проверить, что криптография имеет такие функции, как MD5 (относительно быстрая и вам все равно, что она небезопасна), но она также будет иметь конфликты.

Answer 4

MD5 или SHA . Есть много открытых реализаций, и вряд ли результат даст дублирующий результат.