Поиск быстрой хеш-функции
Я ищу специальную хеш-функцию. Скажем, у меня есть большой список строк, если я заказываю им их значениями хэш-функции, им нужно заказать квази случайным образом.
Наиболее важный момент: это должно быть супер быстро. Я попробовал md5 и sha1, и они используют для большой мощности ЦП.
Столкновения не являются проблемой.
Я использую JavaScript, таким образом, он не должен быть слишком сложным для реализации.
4 ответа
Если скорость имеет первостепенное значение, вы можете реализовать простой специальный хэш, например возьмите первую и последнюю букву и расположите строку сначала по последней, а затем по первой букве. Результат будет выглядеть, как вы говорите, «квазислучайным», и он будет быстрым. Например, часть моего ответа, отсортированного таким образом, будет выглядеть так:
ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you
Посмотрите в Murmur hash. Здесь есть хороший компромисс между пространством и коллизиями:
Похоже, вы хотите, чтобы в хеш-таблице использовалась такая хеш-функция, а не сортировка, используемая для обнаружения дубликатов или подделки.
Поиск в Google даст вам массу информации об альтернативных хэш-функциях. Для начала держитесь подальше от хэшей криптографических подписей (например, MD-5 или SHA-1), они решают другую проблему.
Се , Мурмур , Боб Дженкин .
хорошая страница о хэш-функциях , в которой есть несколько тестов на качество, а также простой хеш S-блока.