2009-03-24 7 views
3

Я ищу алгоритм хэширования, который генерирует целое число со знаком/без знака 31/32 бит в качестве дайджеста для строки utf8 с целью использования вывода для посева prng, такого как LCM Park-Miller-Carta или Мерсенна-Twister.Что такое хороший алгоритм хэширования для посева prng со строкой?

Я изучил FNV1 и FNV1a, но они обеспечивают очень близкие значения для похожих строк, отличающихся своим последним символом; Я хотел бы иметь низкий хеш столкновений, который радикально изменяется при минимальных модификациях входной строки. Производительность не является проблемой.

Мой текущий подход заключается в грязном LCG, который использует коды символов, и простое число в качестве множителей:

a = 524287; 
for (i = 0; i < n; i ++) 
a = (a * string.charCodeAt (i) * 16807 + 524287) % 2147483647; 

Пожалуйста, дайте мне знать о любых лучших альтернатив.

ответ

1

Если вы генерируете 32-битное значение, рассмотрите возможность использования классического CRC32. FNV считается быстрой альтернативой CRC, и вы говорите, что производительность не является проблемой.

3

Использование SHA-2

Это лучший/последний алгоритм хэширования там. Всегда рекомендуется идти со стандартными алгоритмами.

1

Любой криптографически сильный хэш будет иметь нужные свойства, но генерировать больше битов, но простое усечение результата до 32 бит было бы неплохо. Я предполагаю, что криптографическая сила не является фактическим требованием, так что ошибочные (но широко используемые) хэш-схемы, такие как MD5, были бы адекватными - и были бы доступны во многих библиотеках.