5 популярных хеш-функций ..?

Question

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

Я могу подумать, что h (n) = n для целых чисел, где, скажем, мы хотим ранжировать студентов в зависимости от их оценок, т.е.очень ограниченный диапазон возможных значений.

Пожалуйста, помогите с более популярными вариантами, особенно для строк, документов.

Спасибо,

Answer 1

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

Если вы хотите сузить размер ключа (например, только 32-битный), вы все равно можете выбратькриптографическая хеш-функция, такая как SHA-256 и использующая младшие 32 бита.

Можно также представить число в виде строки или в виде двоичных данных и вычислить его криптографический хеш, чтобы обеспечить равномерное распределение ключей.

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

Чтобы лучше подготовиться к собеседованию, вы можетехочу прочитать это .