Анализ целей и выбор хорошей хэш-функции

Question

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

Итак!Давайте поговорим о хэш-функциях и о том, как их выбрать.Как программисту, которому нужно выбрать хорошую хеш-функцию для своей конкретной задачи, нужно выбрать такую?Когда подходит простой и быстрый Фаулер-Нолл-Во?Когда они должны продавать в MurmurHash3 вместо этого?У вас есть ссылки на хорошие ресурсы по сравнению различных вариантов?

Answer 1

Хеш-функция для хеш-таблиц должна иметь эти два свойства

• Однородность все выходы H () должны быть максимально равномерно распределены. Другими словами, для 32-битной хеш-функции вероятность для каждого выхода должна быть равна 1/2 ^ 32. (для n-битов это должно быть 1/2 ^ n). При использовании равномерной хэш-функции вероятность столкновения сводится к минимуму для любого возможного ввода.
• Низкие вычислительные затраты Ожидается, что хеш-функции для таблиц будут FAST по сравнению с криптографическими хеш-функциями, где скорость торгуется для сопротивления прообразу (например, это трудно найти сообщение по заданному хэш-значению) и сопротивление столкновению .

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

Answer 2

Если ваши хеш-ключи являются строками (или другими данными переменной длины), вы можете посмотреть эту статью Рамакришны и Зобеля.Они измеряют несколько классов хеш-функций (для скорости и низких столкновений) и демонстрируют класс, который лучше, чем обычные хеш-функции Бернштейна.