String to Integer Hashing Function with Precision

Question

Я хочу, чтобы hash массив char в 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 бит случайных входов, из-за birthday paradox.

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

Это, как говорится, here несколько альтернатив, которые должны получить вы начали (они предназначены для уменьшения коллизий)

Answer 2

Каждый хэш будет иметь столкновения. Период. Это называется Birthday Problem.

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

Answer 3

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

Answer 4

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