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

Question

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

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

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

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

Answer 1

Вот объяснение в терминах непрофессионала.

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

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

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

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

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

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

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

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

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

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

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

Далее следует технический материал.

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

---

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

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

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

---

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

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

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

Jeach!

Answer 3

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

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

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

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

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

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

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

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

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

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

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

Answer 4

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

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

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] ...) известна как bucket и запускает - возможно, пустой - связанный список значения (или элементы , в данном примере - люди имена )
• каждое значение (например, "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}, в таблице, а затем искать «иск», не зная ее возраста, найти сохраненное значение и восстановить или даже обновить ее возраст
- С Днем Рождения Сью - что интересно не меняет значение хэша, поэтому не требует, чтобы мы переместили запись Сью в другое ведро.

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

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

Существуют и другие способы реализации хеш-таблицы

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

---

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

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

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

Это обычно организовано с математикой, слишком сложной для меня, чтобы впихнуть. Я упомяну один простой для понимания способ - не самый масштабируемый или дружественный к кэшу, но по своей природе элегантный (например, шифрование с помощью одноразовой клавиатуры!) - поскольку я думаю, что он помогает вернуть желаемые качества, упомянутые выше. Допустим, вы хэшировали 64-битные double с - вы можете создать 8 таблиц, каждая из которых содержит 256 случайных чисел (код ниже), а затем использовать каждый 8-битный / 1-байтовый фрагмент представления памяти double для индексации в другая таблица, XOR случайных чисел, которые вы ищете. При таком подходе легко увидеть, что бит (в смысле двоичных цифр), изменяющийся где-либо в 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]];

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

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

Answer 5

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

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

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

Надеюсь, это помогло.

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

Answer 6

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

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

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

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

Answer 7

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

Хеш-таблица оборачивает массив, назовем его 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%, мы можем изменить размер внутреннего массива и переместить все элементы из старого массива в новый.

Answer 8

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

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

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

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

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

Answer 9

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

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

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

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

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

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

Answer 10

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

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

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

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

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