Тесты столкновения хэшей на символах ASCII - PullRequest
2 голосов
/ 11 апреля 2011

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

Причина, конечно, в том, что я хочу получить лучший компромисс между размером (кэш будет представлять несколько миллионов объектов на относительно небольшихсерверы), производительность и безопасность при столкновениях.

Заранее спасибо, Ник

1 Ответ

1 голос
/ 11 апреля 2011

Если вам нужен сильный хеш, я бы предложил что-то вроде Jenkins Hash . Это должно быть менее вероятно, чтобы вызвать столкновения. С точки зрения алгоритмов, вы ищете лавинный тест
Сайт Боба Дженкинса содержит много полезной информации о подобных вещах.
Что касается размера хеш-таблицы, я полагаю, что Кнут рекомендует иметь ее достаточно большой, чтобы при идеальном хеше 2/3 таблицы было бы заполнено, в то время как Дженкинс рекомендует ближайшую большую степень, равную двум

Надеюсь, это поможет!

...