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

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

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

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

Вот объяснение с точки зрения непрофессионала.

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

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

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

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

Но как это можно сделать? Ну, с некоторой предусмотрительностью, когда вы заполняете библиотеку, и большой работой, когда вы заполняете библиотеку.

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

Прелесть этой программы в том, что позже, когда человек возвращается, чтобы прочитать книгу, вы снова вводите название программы и возвращаете тот же номер полки и номер слота, которые были вам изначально предоставлены, и это где находится книга

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

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

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

Итак, вот как работает хеш-таблица.

Технические вещи следует.

Во-первых, есть размер числа. Обычно выходные данные такого алгоритма хеширования находятся в пределах некоторого большого числа, обычно намного большего, чем пространство, которое у вас есть в вашей таблице. Например, допустим, что в библиотеке есть место для одного миллиона книг. Результат вычисления хеша может быть в диапазоне от 0 до одного миллиарда, что намного выше.

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

Скажем, выходной результат алгоритма хеширования находится в диапазоне от 0 до 20, и вы получите значение 17 из определенного заголовка. Если размер библиотеки составляет всего 7 книг, вы считаете 1, 2, 3, 4, 5, 6, а когда вы добираетесь до 7, вы начинаете с нуля. Так как нам нужно сосчитать 17 раз, у нас есть 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, и окончательное число равно 3.

Конечно, вычисление модуля не делается так, оно выполняется с делением и остатком. Остаток от деления 17 на 7 равен 3 (7 переходит 2 раза в 17 в 14, а разница между 17 и 14 равна 3).

Таким образом, вы положили книгу в слот № 3.

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

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

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

Я надеюсь, что это объяснение было немного более приземленным, чем ведра и функции :)

Использование и Линго:

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

Пример из реального мира:

Компания Hash & Co. , основанная в 1803 году и не обладающая какими-либо компьютерными технологиями, имела в общей сложности 300 картотек для хранения подробной информации (записей) примерно для 30 000 своих клиентов. Каждая папка с файлами была четко обозначена своим номером клиента, уникальным номером от 0 до 29 999.

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

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

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

В нашем примере из реального мира наши ведра - это шкафы для документов, а наши записи - это папки с файлами .

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

Как уже упоминал Саймон, я считаю, что очень важным является то, что часть хеширования должна преобразовывать большое пространство (произвольной длины, обычно строки и т. Д.) И отображать его в небольшом пространстве (известного размера, обычно числа) для индексации. Это очень важно помнить!

Таким образом, в приведенном выше примере 30 000 возможных клиентов или около того сопоставляются с меньшим пространством.

Основная идея в этом состоит в том, чтобы разделить весь ваш набор данных на сегменты, чтобы ускорить фактический поиск, который обычно занимает много времени. В нашем примере выше каждый из 300 картотек (статистически) будет содержать около 100 записей. Поиск (независимо от порядка) по 100 записям намного быстрее, чем поиск по 30 000.

Возможно, вы заметили, что некоторые на самом деле уже делают это. Но вместо того, чтобы разрабатывать методологию хеширования для генерации хеш-ключа, в большинстве случаев они просто используют первую букву фамилии. Таким образом, если у вас есть 26 шкафов для хранения документов, в каждом из которых есть буквы от А до Я, вы теоретически просто сегментировали свои данные и улучшили процесс регистрации и поиска.

Надеюсь это поможет,

Jeach!

Это оказывается довольно глубокая область теории, но основная схема проста.

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

Если у вас есть только небольшое пространство для хеширования, вы можете просто интерпретировать эти вещи как целые числа, и все готово (например, 4-байтовые строки)

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

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

Уравновешивание этих двух свойств (и нескольких других) заставило многих людей быть занятыми!

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

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

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

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

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

Много ответов, но ни один из них не очень нагляден , и хеш-таблицы могут легко «щелкнуть» при визуализации.

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

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Несколько моментов:

• каждая из записей массива (индексы [0], [1]...) называется контейнером и запускает - возможно пустой - связанный список значений (иначе говоря, элементы , в данном примере - имена людей )
• каждое значение (например, "fred"с помощью хэша 42) связано с сегментом, [hash % number_of_buckets]например 42 % 10 == [2]; %является оператором по модулю - остаток от деления на количество сегментов
• множественные значения данных могут столкнуться в и быть связаны с одной и той же ведро, чаще всего из - за их хэш - значения сталкиваются после операции по модулю (например 42 % 10 == [2], а 9282 % 10 == [2]), но иногда , потому что хэш - значения являются одинаковыми (например , "fred"и , "jane"как показано , с хэш 42выше)
  • большинство хеш-таблиц обрабатывают коллизии - с немного сниженной производительностью, но без функциональной путаницы - путем сравнения полного значения (в данном случае текста) искомого или вставляемого значения с каждым значением, уже имеющимся в связанном списке в сегменте хеширования

Длина связанного списка относится к коэффициенту загрузки, а не к числу значений

При увеличении размера таблицы хеш-таблицы, реализованные, как указано выше, имеют тенденцию к изменению размера самих себя (т.е. создают больший массив сегментов, создают новые / обновленные связанные списки оттуда, удаляют старый массив), чтобы сохранить соотношение значений к сегментам (или загрузку). фактор ) где-то в диапазоне от 0,5 до 1,0.

Ганс дает фактическую формулу для других коэффициентов нагрузки в комментарии ниже, но для ориентировочных значений: с коэффициентом нагрузки 1 и хэш-функцией криптографической стойкости 1 / e (~ 36,8%) сегментов будет иметь тенденцию быть пустыми, еще 1 / e (~ 36,8%) имеют один элемент, 1 / (2e) или ~ 18,4% два элемента, 1 / (3! E) около 6,1% три элемента, 1 / (4! E) или ~ 1,5% четыре элемента, 1 / (5! E) ~ .3% имеют пять и т. Д. - средняя длина цепочки из непустых сегментов составляет ~ 1,58 независимо от того, сколько элементов в таблице (т.е. есть ли 100 элементов и 100 сегментов, или 100 миллионов) элементов и 100 миллионов блоков), поэтому мы говорим, что поиск / вставка / стирание - это O (1) операций с постоянным временем.

Как хеш-таблица может связывать ключи со значениями

Учитывая реализацию хеш-таблицы, как описано выше, мы можем представить себе создание типа значения, такого как struct Value { string name; int age; };, сравнения равенства и хеш-функций, которые смотрят только на nameполе (игнорируя возраст), и тогда происходит нечто замечательное: мы можем хранить Valueзаписи, как {"sue", 63}в таблице затем выполните поиск «sue», не зная ее возраста, найдите сохраненное значение и восстановите или даже обновите ее возраст
- с днем ​​рождения Сью - что интересно не меняет значение хэша, поэтому не требует, чтобы мы переместили запись Сью в другую ведро.

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

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

Есть и другие способы реализации хеш-таблицы

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

Несколько слов о хэш-функциях

Сильное хеширование ...

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

Это обычно организовано с математикой, слишком сложной для меня, чтобы впасть. Я упомяну один простой для понимания способ - не самый масштабируемый или дружественный к кэшу, но по своей природе элегантный (например, шифрование с помощью одноразовой клавиатуры!) - поскольку я думаю, что он помогает вернуть желаемые качества, упомянутые выше. Допустим, вы хэшировали 64-битные doubles - вы можете создать 8 таблиц по 256 случайных чисел в каждой (код ниже), а затем использовать каждый 8-битный / 1-байтовый фрагмент doubleпредставления памяти для индексации в другую таблицу, XORing случайные числа вы смотрите вверх. При таком подходе легко увидеть, что изменение битов (в смысле двоичных цифр) в любом месте doubleприводит к поиску другого случайного числа в одной из таблиц и абсолютно некоррелированного конечного значения.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Слабое, но часто быстрое хеширование ...

Хеш-функции многих библиотек пропускают целые числа через неизмененные (известные как тривиальная или тождественная хеш-функция); это другая крайность от сильного хеширования, описанного выше. Хэш идентичности чрезвычайносклонность к столкновениям в худших случаях, но есть надежда, что в довольно распространенном случае целочисленных ключей, которые имеют тенденцию к увеличению (возможно, с некоторыми пробелами), они будут отображаться в последовательные сегменты, оставляя меньше пустых, чем случайных листьев хеширования (наши ~ 36,8 % при коэффициенте нагрузки 1, упомянутом ранее), тем самым имея меньше коллизий и меньше длинных связанных списков элементов коллизии, чем достигается случайными отображениями. Также здорово сэкономить время, необходимое для генерации сильного хэша, и если ключи ищутся по порядку, они будут найдены в корзинах поблизости в памяти, улучшая попадания в кэш. Когда ключи не увеличиваются, есть надежда, что они будут достаточно случайными, им не понадобится сильная хеш-функция для полной рандомизации их размещения в сегментах.

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

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

При использовании метода модуля, если у вас есть таблица, скажем, размером 1000, любое значение хеш-значения от 1 до 1000 попадет в соответствующий слот. Любые отрицательные значения и любые значения, превышающие 1000, будут потенциально конфликтующими значениями слотов. Вероятность этого зависит как от метода хеширования, так и от количества элементов, добавляемых в хеш-таблицу. Как правило, рекомендуется делать размер хеш-таблицы таким, чтобы общее количество добавляемых к нему значений было равно примерно 70% его размера. Если ваша хеш-функция хорошо справляется с равномерным распределением, вы, как правило, будете сталкиваться с очень небольшим количеством коллизий между слотами и слотами, и они будут выполняться очень быстро для операций поиска и записи. Если общее количество добавляемых значений заранее неизвестно, сделайте правильную оценку, используя любые средства,

Я надеюсь, что это помогло.

PS - В C # GetHashCode()метод довольно медленный и приводит к коллизиям реальных значений при многих условиях, которые я тестировал. Для реального удовольствия создайте собственную хэш-функцию и старайтесь, чтобы она НИКОГДА не сталкивалась с конкретными данными, которые вы хэшируете, работает быстрее, чем GetHashCode, и имеет довольно равномерное распределение. Я сделал это, используя long вместо значений хеш-кода int-размера, и он работал довольно хорошо для хеш-таблиц до 32 миллионов хеш-таблиц с 0 коллизиями. К сожалению, я не могу поделиться кодом, поскольку он принадлежит моему работодателю ... но я могу показать, что это возможно для определенных областей данных. Когда вы можете достичь этого, хеш-таблица ОЧЕНЬ быстра. :)

Вот как это работает в моем понимании:

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

Допустим, у вас есть 200 объектов, но только 15 из них имеют хеш-коды, начинающиеся с буквы «В». Хеш-таблицу нужно будет только искать и искать по 15 объектам в корзине «B», а не по всем 200 объектам.

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

Коротко и сладко:

Хеш-таблица оборачивает массив, давайте его вызывать internalArray. Элементы вставляются в массив следующим образом:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Иногда два ключа хешируют один и тот же индекс в массиве, и вы хотите сохранить оба значения. Мне нравится хранить оба значения в одном индексе, который легко кодировать, создавая internalArrayмассив связанных списков:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Итак, если бы я хотел получить элемент из моей хеш-таблицы, я мог бы написать:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

Операции удаления так же просто написать. Как вы можете сказать, вставки, поиск и удаление из нашего массива связанных списков почти O (1).

Когда наш internalArray переполняется, возможно, на 85%, мы можем изменить размер внутреннего массива и переместить все элементы из старого массива в новый.

Это даже проще, чем это.

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

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

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

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

Вы берете кучу вещей и массив.

Для каждой вещи вы создаете для нее индекс, называемый хешем. Важным в хеше является то, что он много «разбрасывает»; Вы не хотите, чтобы две одинаковые вещи имели одинаковые хеши.

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

Когда вы просматриваете вещи в хэше, вы проделываете те же самые шаги, выясняете значение хеша, затем смотрите, что находится в корзине в этом месте, и проверяете, ищите ли вы.

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

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

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

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

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

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

Вот еще один способ взглянуть на это.

Я предполагаю, что вы понимаете концепцию массива A. Это то, что поддерживает операцию индексации, где вы можете получить I-й элемент, A [I], за один шаг, независимо от того, насколько велика A.

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

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

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

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

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

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

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

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

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

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

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

(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 - это любое пространство, в котором хранятся значения - здесь я сохранил его как индекс массива, но, возможно, это также место в памяти.