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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Скажем, результат хеш-алгоритма находится в диапазоне от 0 до 20, и вы получаете значение 17 из определенного заголовка. Если размер библиотеки составляет всего 7 книг, вы считаете 1, 2, 3, 4, 5, 6, а когда вы дойдете до 7, вы начнете снова с 0. Поскольку нам нужно считать 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 картотек, каждый из которых содержит буквы от A до Z, вы теоретически только что сегментировали свои данные и улучшили процесс регистрации и поиска.

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

Джич!

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

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

Если у вас есть только небольшое пространство для хеширования, вы можете просто интерпретировать эти вещи как целые числа, и все готово (например, 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], _4 _...) известна как корзина и запускает - возможно, пустой - связанный список значений (он же элементы, в этом примере - имена людей)
• каждое значение (например, "fred" с хешем 42) связано с сегментом [hash % number_of_buckets], например 42 % 10 == [2]; % - это оператор по модулю - остаток при делении на количество ведра
• multiple data values may collide at and be linked from the same bucket, most often because their hash values collide after the modulo operation (e.g. 42 % 10 == [2], and 9282 % 10 == [2]), but occasionally because the hash values are the same (e.g. "fred" and "jane" both shown with hash 42 above)
  • most hash tables handle collisions - with slightly reduced performance but no functional confusion - by comparing the full value (here text) of a value being sought or inserted to each value already in the linked list at the hashed-to bucket

Если размер таблицы увеличивается, хеш-таблицы, реализованные, как указано выше, имеют тенденцию изменять размер (т. Е. Создавать больший массив сегментов, создавать новые / обновленные связанные списки на их основе, удалять старый массив), чтобы сохранить соотношение значений к сегментам (также известное как < em> коэффициент загрузки) где-то в диапазоне от 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) ~ 0,3% имеют пять и т. Д. - средняя длина цепочки из непустых сегментов составляет ~ 1,58 независимо от того, сколько элементов находится в таблице (т.е. есть ли 100 элементов и 100 сегментов, или 100 миллионов элементов и 100 миллионов сегментов), поэтому мы говорим, что поиск / вставка / стирание - это O (1) операции с постоянным временем.

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

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

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

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

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

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

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

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

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&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% от ее размера. Если ваша хеш-функция хорошо справляется с равномерным распределением, вы, как правило, будете сталкиваться с очень небольшим количеством или отсутствием коллизий между корзинами и слотами, и она будет работать очень быстро как для операций поиска, так и для операций записи. Если общее количество добавляемых значений заранее неизвестно, сделайте хорошее предположение, используя любые средства, а затем измените размер своей хеш-таблицы, как только количество добавленных к ней элементов достигнет 70% емкости.

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

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

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

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

Допустим, у вас есть 200 объектов, но только 15 из них имеют хэш-коды, начинающиеся с буквы «B». В хэш-таблице нужно будет искать и перебирать только 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-представления имени человека, зашифрованный в каком-то порядке. Важно только то, что вы не хотите, чтобы слишком много людей хешировали в одно ведро, потому что скорость зависит от того, сколько ведер останется маленьким.

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

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

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

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

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

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

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

Основная мысль

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

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

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

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

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

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

              +---------+
            |\|   hash  |/| --> hash code
   data --> |/| function|\|
              +---------+

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

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

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

Когда у нас есть хеш-функция, мы можем построить очень простую хеш-таблицу. Мы сделаем ряд ведер, которые можно рассматривать как аналог ящиков в нашем комоде. Чтобы сохранить элемент в хэш-таблице, мы вычислим хэш-код объекта и будем использовать его в качестве индекса в таблице, что аналогично выбору, в какой ящик помещается этот элемент. Затем мы помещаем этот элемент данных в ведро с этим индексом. Если это ведро было пустым, отлично! Мы можем положить туда предмет. Если это ведро заполнено, у нас есть несколько вариантов того, что мы можем сделать. Простой подход (называемый цепное хеширование < / a>) заключается в том, чтобы рассматривать каждое ведро как список элементов, так же, как ваш ящик для носков может хранить несколько носков, а затем просто добавлять элемент в список по этому индексу.

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