Как работает хэш-часть в хэш-картах?

Question

Итак, эта прекрасная картина есть в статье хеш-карт в Википедии:

Пока все ясно, кроме хеш-функции в середине.

• Как функция может генерировать правильный индекс из любой строки? Индексы тоже целые в реальности? Если да, то как функция может вывести 1 для John Smith, 2 для Lisa Smith и т. Д .?

Answer 1

Это одна из ключевых проблем хэш-карт / словарей и так далее. Вы должны выбрать хорошую хэш-функцию. Очень плохой, но быстрой хэш-функцией может быть длина ключей. Вы сразу видите, что вы получите много коллизий (разные ключи, но один и тот же хеш). Другая плохая хеш-функция может быть значением ASCII первого символа вашего ключа. Много столкновений тоже.
Таким образом, вам нужна функция, которая намного лучше, чем эти две. Вы можете добавить (xor) все значения ASCII ключевых символов и, например, смешать длину. На практике вы часто зависите от значений (полей) объекта, который хотите хэшировать (одни и те же значения дают одинаковый тип хэш =>). Для справочных типов вы можете смешивать, например, в ячейке памяти.

В вашем примере это очень сильно упростило. Никакая реальная хеш-функция не сопоставит эти ключи с последовательными числами.

Может быть, вы хотите прочитать один из моих предыдущих ответов на хеш-карты

Answer 2

Простая хеш-функция может быть следующей:

$hash = $string[0] % HASH_TABLE_SIZE;

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

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

Answer 3

Есть действительно хорошая статья о том, как хэш-функции (и обнаружение / разрешение коллизий) в MSDN:

Часть 2: Очередь, стек и Hashtable

Вы можете перейти к заголовку Сжатие порядкового индексирования с помощью функции хеширования

Существуют некоторые фрагменты, специфичные для .NET (когда они говорят о том, какой алгоритм Hash .NET используется по умолчанию), но по большей части это не зависит от языка.

Answer 4

Все, что требуется от хеш-функции, - это то, что она возвращает одно и то же целое число, если тот же ключ. Технически хеш-функция, которая всегда возвращает «1», не является неправильной.

Answer 5

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

Что касается вашего конкретного вопроса, как строка становится числом. Любая строка состоит из символов (J, o, h, n ...), и символы можно интерпретировать как числа (в компьютерах). Стандарты ASCII и UTF связывают определенные значения с определенными символами, поэтому результат является детерминированным и всегда одинаковым на всех компьютерах. Таким образом, хэш-функция выполняет операции с этими символами, обрабатывая их как числа и получая другое число (вывод). Например, вы можете просто суммировать все значения и использовать операцию по модулю для ограничения диапазона результирующего значения.

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