Как работает хеш-таблица?

Question

Я ищу объяснение того, как работает хеш-таблица - на простом английском языке для простого человека, как я!

Например, я знаю, что он берет ключ, вычисляет хеш (я ищу объяснение, как), а затем выполняет какой-то модуль по модулю, чтобы определить, где он находится в массиве, где хранится значение, но там мои знания прекращаются.

Может кто-нибудь прояснить этот процесс?

Редактировать: Я не спрашиваю конкретно о том, как вычисляются хеш-коды, но общий обзор того, как работает хеш-таблица.

Answer 1

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

Как объяснил Саймон, хеш-функция используется для отображения из большого пространства в небольшое пространство. Простая наивная реализация хеш-функции для нашего примера может взять первую букву строки и отобразить ее в целое число, поэтому у «аллигатора» есть хэш-код 0, у «пчелы» хэш-код 1 ». зебра "будет 25 и т. д.

Далее у нас есть массив из 26 сегментов (может быть ArrayLists в Java), и мы помещаем в него элемент, соответствующий хэш-коду нашего ключа. Если у нас более одного элемента с ключом, начинающимся с одной и той же буквы, они будут иметь одинаковый хеш-код, поэтому все будут идти в корзину для этого хэш-кода, поэтому в корзине должен быть выполнен линейный поиск, чтобы найти конкретный предмет.

В нашем примере, если бы у нас было всего несколько десятков предметов с клавишами, охватывающими алфавит, это бы работало очень хорошо. Однако, если бы у нас было миллион элементов или все ключи начинались с «a» или «b», то наша хеш-таблица не была бы идеальной. Чтобы получить лучшую производительность, нам нужна другая хеш-функция и / или несколько блоков.

Answer 2

Хеш-таблица полностью работает на том факте, что практические вычисления следуют модели машины с произвольным доступом, то есть значение по любому адресу в памяти может быть получено за O (1) или постоянное время.

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

Как правило, в приложениях размер юниверса ключей очень велик, чем количество элементов, которые я хочу добавить в хэш-таблицу (я не хочу тратить 1 ГБ памяти на хэш, скажем, 10000 или 100000 целочисленных значений, потому что в двоичном представлении они имеют длину 32 бита). Итак, мы используем это хеширование. Это своего рода смешанная «математическая» операция, которая отображает мою большую вселенную на небольшой набор значений, которые я могу разместить в памяти. В практических случаях часто пространство хеш-таблицы имеет тот же «порядок» (big-O), что и (количество элементов * размер каждого элемента), поэтому мы не тратим много памяти.

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

• Используйте пространство, которое должно было быть выделено для значения, как ссылку на связанный список. В этом связанном списке будут храниться одно или несколько значений, которые находятся в одном и том же слоте во многих сопоставлениях. Связанный список также содержит ключи, которые помогут кому-то, кто приходит на поиски. Это как многие люди в одной квартире, когда приходит разносчик, он идет в комнату и специально спрашивает парня.
• Используйте двойную хеш-функцию в массиве, которая каждый раз выдает одну и ту же последовательность значений, а не одно значение. Когда я иду, чтобы сохранить значение, я вижу, свободна ли требуемая область памяти или занята. Если это бесплатно, я могу хранить свое значение там, если оно занято, я беру следующее значение из последовательности и так далее, пока не найду свободное место и не сохраню свое значение там. При поиске или получении значения я возвращаюсь по тому же пути, который указан в последовательности, и в каждом месте запрашиваю vaue, будет ли оно там, пока не найду его или не найду все возможные местоположения в массиве.

Введение в алгоритмы, разработанное CLRS, дает очень хорошее представление о теме.

Answer 3

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

Answer 4

Для всех, кто ищет язык программирования, вот как это работает. Внутренняя реализация расширенных хеш-таблиц имеет много сложностей и оптимизаций для выделения / освобождения хранилища и поиска, но идея верхнего уровня будет во многом такой же.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

, где calculate_bucket_from_val() - это функция хеширования, где должна происходить вся магия уникальности.

Правило большого пальца: Для вставки заданного значения ведро должно быть УНИКАЛЬНО и ДОБИВАЕМЫМ ИЗ ЗНАЧЕНИЯ, которое оно должно хранить. Bucket - это любое пространство, в котором хранятся значения - поскольку здесь я сохранил его как индекс массива, но это может быть также и место в памяти.