В поисках быстрой хэш-функции

Question

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

Самый важный момент: это должно быть очень быстро. Я пробовал md5 и sha1, и они используют слишком много ресурсов процессора.

Столкновения не проблема.

Я использую javascript, поэтому он не должен быть слишком сложным для реализации.

Answer 1

Взгляните на хэш Murmur. У этого есть хороший компромисс пространства / столкновения:

http://sites.google.com/site/murmurhash/

Answer 2

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

Поиск в Google даст вам массу информации об альтернативных хэш-функциях. Прежде всего, держитесь подальше от криптографических хэшей подписи (например, MD-5 или SHA-1), они решают другую проблему.

Вы можете прочитать это , или это , или это , чтобы начать с.

Answer 3

Hsieh , Шепот , Боба Дженкина * приходит мне в голову.
хорошая страница о хэш-функциях , которая имеет несколько тестов на качество и простой хэш S-box.

Answer 4

Если скорость имеет первостепенное значение, вы можете реализовать простой специальный хеш, например, возьмите первую и последнюю букву и упорядочите строку по последней, а затем по первой букве. Результат будет выглядеть, как вы говорите, «почти случайно», и он будет быстрым. Например, часть моего ответа, отсортированного таким образом, будет выглядеть так:

ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you