#data-structures #hash
#структуры данных #хэш
Вопрос:
Я появлюсь на собеседовании в Google через неделю.Я понимаю, что хэш-таблицы, хэш-карты, хэш-функции очень полезны и пригодятся во многих вопросах интервью, таких как словарь, сортировка по корзинам, для проверки дублирования всего документа, URL-адреса и т.д., Будь то в строках или целых числах. Мне интересно, каковы некоторые из популярных хэш-функций как для целых чисел, так и для строк.
Одна из них, о которой я могу подумать, это h (n) = n для целых чисел, где, скажем, мы хотим ранжировать студентов в зависимости от их оценок, т. е. очень ограниченного диапазона возможных значений.
Пожалуйста, помогите с более популярными вариантами, особенно для строк, документов.
Спасибо,
Комментарии:
1. Извините, но это действительно заслуживает оценки -1 за отсутствие исследовательских усилий.
Ответ №1:
Для строк можно использовать криптографический хэш строки в качестве ключа для хэш-таблицы. Обычно это приводит к равномерному распределению хэш-ключей, что является хорошим свойством хэш-таблицы.
Если вы хотите сузить размер ключа (например, только 32 бита), вы все равно можете выбрать криптографическую хэш-функцию, такую как SHA-256, и использовать младшие 32 бита.
Число также можно представить в виде строки или двоичных данных и вычислить его криптографический хэш для обеспечения равномерного распределения ключей.
Как только ваши ключи распределены равномерно, вам не нужно использовать сложную хэш-функцию — вы можете просто распределить диапазон ключей по ячейкам одинакового размера.
Чтобы лучше подготовиться к собеседованию, вы можете также прочитать это.