Хеш таблицы


Содержание

Хеш-таблицы

Один из наиболее эффективных способов реализации словаря — хеш-таблица. Среднее время поиска элемента в ней есть O(1), время для наихудшего случая — O(n). Прекрасное изложение хеширования можно найти в работах Кормена[1990] и Кнута[1998]. Чтобы читать статьи на эту тему, вам понадобится владеть соответствующей терминологией. Здесь описан метод, известный как связывание или открытое хеширование[3]. Другой метод, известный как замкнутое хеширование[3] или закрытая адресация[1], здесь не обсуждаются. Ну, как?

Теория

Хеш-таблица — это обычный массив с необычной адресацией, задаваемой хеш-функцией. Например, на hashTable рис. 3.1 — это массив из 8 элементов. Каждый элемент представляет собой указатель на линейный список, хранящий числа. Хеш-функция в этом примере просто делит ключ на 8 и использует остаток как индекс в таблице. Это дает нам числа от 0 до 7 Поскольку для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм гарантирует допустимые значения индексов.

Рис. 3.1: Хеш-таблица

Чтобы вставить в таблицу новый элемент, мы хешируем ключ, чтобы определить список, в который его нужно добавить, затем вставляем элемент в начало этого списка. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует разместить в списке, на начало которого указывает hashTable[3]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий.

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

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай — когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько из возможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 битах, unsigned short int — в 16, unsigned long int — в 32.

    Деление (размер таблицыhashTableSizeпростое число). Этот метод использован в последнем примере. Хеширующее значение hashValue, изменяющееся от 0 до (hashTableSize — 1), равно остатку от деления ключа на размер хеш-таблицы. Вот как это может выглядеть:

Здесь Rand8 — таблица из 256 восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным (Pearson [1990]).
Исключающее ИЛИ для строк переменной длины (размер таблицы

размер время размер время
1 869 128 9
2 432 256 6
4 214 512 4
8 106 1024 4
16 54 2048 3
32 28 4096 3
64 15 8192 3

Таблица 3.1: Зависимость среднего времени поиска (чs) от hashTableSize. Сортируются 4096 элементов.

Реализация

В реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable. В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.

ЗлостныйКодер

Программирование, Алгоритмы, С++, C#, Java, Python и другие вещи

четверг, 17 января 2013 г.

Хеш-таблица (Hash-Table). Реализация C++.

Чтобы понять, что такое хеш-таблица, вспомним массив. Мы можем получить доступ к элементу с помощью его ключа, причем может быть такой случай, что есть ячейки содержащие элементы и есть не содержащие.
Представим ситуацию, что нам нужно найти элемент, например, массив состоит из строк большой длины. Нам придется нашу подстроку поиска сравнивать со всеми элементами массива, что неудобно, так как поиск займет O(n). НО мы хотим O(1). Решение есть! Использовать специальную хеш функцию, для того, чтобы мы имели доступ по индексу.

  • Каждой строке соответствует индекс равный (n=длина строки-1). Например: строка «Alex» индекс 3. Вот так можно записать строки.
  • Хеш функция у нас будет: Hash_Func(string)=Strlen(string) (то есть вычисление длины).
  • Доступ к массиву мы получаем вот так: Mas[Hash_Func(string)].

length value
————————
2 «joe»
3 «Alex»
4 «Pavel»
Но! вот в чем беда! Если мы хотим вставить еще 1 имя, например «Petr», то этому имени будет соответствовать ОДИН И ТОТ ЖЕ КЛЮЧ 3, который является индексом 3. Это называется Коллизией, когда один и тот же ключ указывает на несколько значений ключа.
Иллюстрация коллизии (2 ключа относятся к одной и той же ячейки массива, ключи k2 и k3):

Разрешение случаев с коллизией является важной задачей Computer Science. Решениями проблемы являются:

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

Возвращаясь к нашему примеру с именами, переделаем его в соответствии с новым методом:
length value
————————
2 *head1 [«Joe»->»Rex»->Null]
3 *head2 [«Alex»->»Petr»->»Oleg»->Null]
4 *head3 [«Pavel»->Null]
В этом примере 0,1,5 элементы указатели равны Null
Процедура вставки происходит так: Вычисляется хеш-функция от строки и вставляется в голову списка (push_front) на определенный индекс равный значению функции.
Вставка происходит за O(1).
Поиск или удаление элемента зависит от длины списка, худший случай: O(n) — когда, все элементы хешируются в одну и ту же ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка k=n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. В этом случае время поиска: O(1+k), это показано в книжке Кормана, могу скинуть ссылку на нее, если интересно.
Добавлю, что в случае, когда коэффициент заполнения будет слишком велик, надо будет увеличить размер массива и, возможно, перестроить таблицу.

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

Общий прием состоит в следующем: если хеш-функция вырабатывает позицию для первого кандидата i = Hash_Func(key) Mod (capacity) , то последующие позиции определяются как i + increment , i +2 * increment , i +3 * increment и так далее, все по модулю capacity . Величина increment вычисляется как:
Hash_Func(key) Mod (capacity -1)

i,i1,i2 ячейки заняты, i=2, i1=4, i2=6, i3=8, capacity=11
Последующие index=i+increment (increment = 2 Mod 10 = 2 )

Хеш-таблицы имеют очень большое практическое применение:

  • Для поиска информации о водители лишь по его номеру в водительском удостоверении.

  • Таблица символов компилятора. Хеширование является методом ускорения поиска. Компилятор встре­чает некоторую лексему и пытается найти ее в своей базе данных или таб­лице символических имен. Таблица символических имен современного компилятора в MS Windows может содержать несколько тысяч или десятков тысяч лексем. Для ускорения поиска был придуман следующий прием. Компилятор, найдя лексему в тексте программы, определяет ее хеш-ключ. Наша лексема — это просто слово, состоящее из последовательности кодов символов. Для определения хеш-кода следует сложить все коды символов. Лексем с таким хеш-кодом в базе данных уже значительно меньше. Компи­лятор определяет номер списка с заданным кодом и перебирает этот спи­сок, а не всю базу данных.
  • При программировании шахмат тоже используется хеширование. Основная особенность состоит в том, что хеш-индекс должен очень точно отражать позицию, и поиск должен производиться максимально быстро. У нас даже нет времени на перебор списков с одним индексом. Списков, как правило, нет вообще. Для каждого значения хеш-ключа существует только одна по­зиция. Если возникла коллизия и встретилась позиция с таким же ключом, то она записывается поверх прежней. Зачем при программировании шахмат и других подобных игр хеширование и запоминание позиций? Дело в том, что при переборе мы имеем не дерево игры в прямом смысле, а граф. По­зиции повторяются через некоторое количество полуходов, и даже в одну и ту же позицию можно прийти различными путями. Можно воспользоваться некоторой информацией о позиции, которая уже встречалась. Самое про­стое и эффективное — это использовать позицию, чтобы улучшить порядок ходов. Это особенно выразительно при итеративных углублениях. Улучше­ние упорядочивания ходов — основное назначение хеш-таблицы. Переста­новки или повторы позиций тоже играют свою роль. Особенно их много в конце игры.
  • Для баз данных телефонных номеров.
  • Каталог книг.
  • Для хранения паролей пользователей.
  • Браузер хранит адреса посещенных страниц в хеш-таблице.

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

Хэш-таблицы: теория и практика

Оригинал: Hash Tables-Theory and Practice
Автор: Mihalis Tsoukalos
Дата публикации: 12 октября 2015 г.
Перевод: A.Панин
Дата перевода: 13 октября 2015 г.

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


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

Постановка задачи

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

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

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

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

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

Теоретическая информация

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

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

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

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

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

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

В хэш-таблице с «корректным» количеством корзин средняя цена каждой операции поиска значения не зависит от количества элементов таблицы.

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

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

Хэш-таблицы также имеют некоторые недостатки:

Они не предназначены для хранения отсортированных данных. Использование хэш-таблицы для сортировки данных не является продуктивным.

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

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

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

Хэш-таблицы работают достаточно неэффективно при наличии множества коллизий.

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

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

Рисунок 1. Простая хэш-таблица

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

Не следует создавать слишком большое количество корзин; следует создавать ровно столько корзин, сколько требуется.

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

Хэш-функция должна генерировать различные значения для похожих ключей.

Каждая корзина должна содержать одно и то же количество ключей или, по крайней мере, их сопоставимые количества (это очень желательное свойство).

Илон Маск рекомендует:  Borland delphi 4 0 для начинающих элементы управления activex

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

Добавление, удаление и поиск элементов

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

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

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

Реализация на языке программирования C


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

В Листинге 1 показан исходный код приложения на языке C из файла ht1.c.

Более удачная реализация хэш-таблицы на языке программирования C

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

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

Тестирование производительности

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

Все программы компилируются с помощью следующей команды:

Надежная утилита time вывела следующую информацию после четырехкратного исполнения программы ht1 с использованием четырех различных размеров хэш-таблицы:

На Рисунке 2 представлен график времени исполнения программы на основе исходного кода из файла ht1.c с четырьмя различными значениями константы TABLESIZE. Проблема реализации хэш-таблицы из файла ht1.c заключается в том, что производительность хэш-таблицы с 101 корзиной практически равна производительности хэш-таблицы с 1001 корзиной!

Рисунок 2. Время исполнения программы на основе исходного кода из файла ht1.c при использовании четырех различных значений константы TABLESIZE

А это результаты исполнения программы на основе исходного кода из файла ht2.c:

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

Рисунок 3. График времени исполнения программы на основе исходного кода из файла ht2.c при использовании пяти различных значений константы TABLESIZE

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

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

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

Рисунок 4. Количество ключей в каждой корзине двух хэш-таблиц с различным количеством корзин

Заключение

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

Задача: спроектируйте и реализуйте хэш-таблицу

Что такое хэш-таблица?

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

О других структурах данных вы можете прочитать в нашем разделе.

Условие задачи

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

Решение

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

items — массив связных списков, а items[i] — связный список всех объектов с клю­чами, которым сопоставляется индекс i (все коллизии для индекса i ). Вроде бы все работает… пока мы не задумаемся о коллизиях. Допустим, у нас очень простая хэш-функция, которая использует длину строки:

Ключи jim и bob будут соответствовать одному индексу массива, хотя это разные ключи (с одинаковой длиной строки). Нам нужно произвести поиск по связному списку, чтобы найти правильные объекты, соответствующие ключам. Но как это сделать? Ведь в связном списке хранится значение, а не исходный ключ. Одно из возможных решений — создание другого объекта (Cell), связывающего ключи со значениями. В этой реализации наш связный список будет иметь тип Cell. Следующий код использует эту реализацию:

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

Если вас заинтересовала данная тема, то вы можете прочитать интересный материал о сопоставлении хэш-таблиц и map в С++.

Хеш-таблицы.

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

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

Генерация этого уникального числа получается в результате вычисления хеш-функции на основе его ключа. Например, для организации словаря на основе хеш-таблицы вам нужно преобразовать значение ключа(само слово) в соответствующий ему адрес в массиве. Размер массива должен быть представлен простым числом, что снизит вероятность коллизий. Также при вычислении ключа нужно следить за тем, чтобы вычисленный адрес не оказался слишком большим, а остался в пределах от 0 до M-1(где M — длина массива). Для избежания таких проблем при вычислении хеш-значения можно взять остаток от деления полученного числа на размер массива. Это можно сделать с помощью операции mod(вычисление остатка от деления h(k) = K mod M).

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


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

Методы разрешения коллизий.

Основных методов два — это открытая адресация и уже упоминавшийся нами метод цепочек.

В методах открытой адресации в случае, если ячейка уже занята, то выполняется поиск следующей незанятой ячейки, адрес которой вычисляется с некоторым смещением относительно нее. Мы реализуем разрешении коллизий методом линейного пробирования. В нем смещение равно единице и алгоритм последовательно перемещается от одной ячейки к другой, пока не будет найдена незанятая ячейка. То есть адреса будут рассчитываться, как x + 1, x + 2, x + 3 и т.д.

Другая вариация открытой адресации — квадратичное пробирование. Смещение на каждом шаге будет равно квадрату номера шага, и адреса будут получены по формулам x + 1, x +4, x + 9 и т.д.

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

Наконец, в методе цепочек каждая из M ячеек массива содержит в себе связный список. Если два элемента хешируются в один список, то они просто последовательно туда добавляются. Конечно, теоретически это может снизить скорость поиска. Но практически, мы не потеряем эффективность, если размер таблицы будет достаточно большой. И, даже если мы экономим память и для нас это приоритетно, то среднее количество элементов в каждом списке на самом деле будет невелико и рассчитываться по формуле N/M, где N — количество элементов в таблице. Данный метод наглядно изображен на рисунке в самом начале.

Хеш-функции.

Различных хеш-функций существует большое множество. Мы в нашем примере будем работать со строками. По этому для преобразования строки в число используем следующую несложную хеш-функцию(данный пример есть в книге Седжвика «Алгоритмы Java»):

Хеш-таблицы

Пример из жизни:

Чтобы разобраться что такое хеш-таблицы и для чего они нужны стоит привести очень интересный и показательный пример из жизни. Представьте, что вы работаете в библиотеке и необходимо каждому клиенту оперативно выдавать какую-нибудь книгу. Конечно, можно заранее отсортировать книги по алфавиту и производить поиск, но когда книг действительно много и поиск займет достаточное время, что может сказаться на настроениях читателей. А что если придумать набор правил при котором по названию книги будет производится мгновенный перевод в номер полки или стилажа (например, номер стилажа равен 10+[век в котором творил писатель]). Тоже самое можно сказать про некую базу клиентов спортивного клуба, у которых есть уникальная карта клиента. По фамилии, имени и отчеству можно сразу определить информацию по карте, например, количество оставшихся занятий и т.д. Или быстрый поиск цены на отдельный вид товара или абонента в телефоне. Наконец, еще один показательный пример который приходит в голову — это быстрое преобразование веб-сайта (www.adit.io) в IP — адрес (173.255.248.55) для поиска ресурса в сети.

Итак, все эти задачи объединяет одно — есть некое правило которое перерабатывает определенный смысловой маркер(вид товара, имя абонента, название книги) в нужное значение (цену, номер телефона абонента, место книги) . Для чего это нужно спросите Вы? Во-первых, такой подход призван обеспечить быстрый поиск значений разнообразных данных (даже тех, которые могут вновь добавляться). Во-вторых, выполняется необходимое преобразование или получение «понятного значения» в требуемый вид, как пример с IP-адресом. И в третьих, формируется уникальность или неповторяемость каждого объекта, что крайне важно например в некоторых задачах (таких как сохранение сессий отдельных пользователей на сервере или проверка передачи данных и т.д). Но существует несколько подводный камней такого рода решений.

Как говорится легко сказать — трудно сделать! Как было указано в примере с библиотекой необходимо придумывать некое правило хранения книг по названию. Таким образом, нужно не только прибавить 10 к значению века, в котором творил писатель, но и помнить в каком веке творил писатель. А что если писатель работал в 18 и 19 веках? А не получится ли так, что два писателя работали примерно в одних временных рамках? Конечно получится, поэтому надо очень постараться придумать настолько простое правило, чтобы не требовало больших ресурсов и услий при этом обеспечивало уникальность каждой сущности или объекта.

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

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

  • Добавление новой пары ключ-значение
  • Поиск значения по ключу
  • Удаление пары ключ-значение по ключу

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

Теперь, если запросить номер телефона «John Smith» (как показано на рисунке), то хеш-функция обработает данную строку и вернет ключ со значением 2. Обратившись ко второму элементу массива получим номер телефона = 521-1234.

Как отмечалось выше, для реализации структуры данных в виде хеш-таблицы, необходимо предусмотреть такую функцию, которая удовлетворяла бы следующим условиям:

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

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

Хеширование с цепочками (открытое хеширование) — позволяют множеству элементов занимать одну и ту же позицию в хэш-таблице. Основной смысл данного метода заключается в формировании связного списка в ячейках массива. Таким образом, если для двух разных элементов вычисляется одинаковый хеш, то этот элемент добавляется в связный список. К примеру для двух абонентов: «John Smith» и «Sandra Dee» получился одинаковый хеш = 152, а значит необходимо поместить второй элемент в связный список. Обычно помещается пара ключ-значение для поиска в этом связном списке соотвествующего значения. При поиске, как и при удалении приходится проходить по списку (цепочкам), сравнивая ключи между собой на эквивалентность, пока не доберёмся до нужного.

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

Илон Маск рекомендует:  Перфорированная рамка

Хеширование с открытой индексацией (закрытое хеширование). В отличии от первого способа происходит сохранение всех элементов в ячейках массива без использования связный списков. Сохранение происходит с помощью процедуры линейного пробирования (исследования). В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Если достигается конец массива, то происходит «перескакивание» в начало массива и продолжается последовательный перебор ячеек. Например, в конкретном случает происходит коллизия двух ключей «John Smith» и «Sandra Dee» при этом в 152 сохраняется «John Smith», а второй элемент начинает «искать» (перебирать) свободное место. К счастью следующая ячейка осказалось пустой и в нее записался объект с ключом «Sandra Dee».

Если 153 ячейка оказалась бы заполненной, то происходил бы последовательный перебор ячеек т.е. 154, 155, 156 и т.д. Как только последующая ячейка оказалось бы пустой, то элемент сохранился бы в эту ячейку. В данном случае может возникнуть так называемая проблема кластеризация. Это явление создания длинных последовательностей занятых ячеек, которое увеличивает среднее время поиска в таблице. Для преодоления этой проблемы используется способ квадратичного пробирования и двойного хеширования.

Квадратичного пробирование. Интервал между ячейками с каждым шагом увеличивается на константу. Вместо использования константного значения “пропуска”, мы используем повторную хэш-функцию, которая инкрементирует хэш-значение на 1, 3, 5, 7, 9 и так далее. Например, Это означает, что если первое хэш-значение равно h «> h , то последующими будут h + 1 «> h +1 , h + 4 «> h +4 , h + 9 «> h + 9 , h + 16 «> h + 16 и так далее.

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

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

Метод свертки: хеш-функция формируется на основе деления элементов на состовляющие одинаковой величины. Далее, полученные кусочки (могут инвертироваться т.е. менять порядок разрядов на обратный) складываются вместе и над этой суммой производится целочисленное деление на кол-во всех элементов в hash-таблице. Таким образом, если ключом является строка ее необходимо разбить на отдельные символы и преобразовать в цифровое представление. Если строка содержит числа можно сформировать группы чисел, например, 521-1234 можно представить в виде 52, 11, 23, 4. В случае с «John Smith» преобразуем символы в численное представление 48, 97, 147, 198, 250, 303, 357, 412, 468.

Замечание: Внимательный читатель обратил вниманине на то, что если строка представляет из себя аннаграмму (слова, которые содержат аналогичные буквы [anna, nana]) , будут всегда порождать коллизии. Для того чтобы избежать этого необходимо умножить каждый элемент на номер позиции буквы в строке.

Шаг 1. Разбиваем элемент на составные части в виде чисел;

Шаг 2. Суммируем полученные числа (если используются анаграммы умножаем каждое число на его позицию);

Шаг 3. Производим целочисленное деление на кол-во элементов хеш-таблицы.

Метод средних квадратов. Напоминает метод свертки только после получения значения в виде суммы элементов производится операция возведения в квадрат и выделение из числа средних цифр (разрядов). Как отмечалось выше 521-1234 можно представить в виде 52, 11, 23, 4. Соотвественно, сумма = 90. Данное число нужно возвести в квадрат = 8100 и выбрать средние значения т.е. 10. После этого произвести деление с остатком.


Шаг 1. Разбиваем элемент на составные части в виде чисел;

Шаг 2. Суммируем полученные числа (если используются анаграммы умножаем каждое число на его позицию);

Шаг 3. Возводим в квадрат получившиеся число и производим выделение средних разрядов;

Шаг 4.Производим целочисленное деление на кол-во элементов хеш-таблицы.

Хеш-функция. Воспользуемся методом свертки. Для этого определим длину строки на строке (строка 3) и последовательно суммируем целочисленное представление символов (строка 5 ). Осуществляем целочисленное деление полученной суммы и возвращаем полученный хеш.

Хеш-таблица (hashtable) на языке C#

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

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

Метод цепочек (открытое хеширование) — все элементы данных с совпадающем хешем объединяются в список.

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

В данном примере мы будем реализовывать первый вариант.

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

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

Insert — добавить новый элемент в хеш-таблицу

Delete — удалить элемент из хеш-таблицы по ключу

Search — получить значение по ключу

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

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

Bits of Mind

Заметки о программировании, и не только…

Введение в хеш-таблицы

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

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

Введение в хеш-таблицы

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

  • Добавление новой пары ключ-значение
  • Поиск значения по ключу
  • Удаление пары ключ-значение по ключу

Так, простой пример сессии работы с хеш-таблицой может выглядеть так (пример на Python):

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

Что же такое хеширование? Идея хеширования основана на распределении ключей в обычном массиве H[0..m-1]. Распределение осуществляется вычислением для каждого ключа элемента некоторой хеш-функции h. Эта функция на основе ключа вычисляет целое число n, которое служит индексом для массива H. Конечно, необходимо придумать такую хеш-функцию, которая бы давала различный хеш-код для различных объектов.

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

Где m – размер хеш-таблицы, C – константна, большая любого ord(c), а ord() – функция, возвращающая числовой код символа. Для каждого типа данных можно разработать свою хеш-функцию. Однако есть основные требования к хеш-функции: она должна распределять ключи по ячейкам хеш-таблицы как можно более равномерно, и должна просто вычисляться.

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

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

Хеширование с цепочками

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


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

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

Хеширование с открытой адресацией

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

Для разрешения же коллизий применяются несколько подходов. Самый простой из них – это метод линейного исследования. В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Так, при достижении последнего индекса таблицы, мы перескакиваем в начало, рассматривая её как «цикличный» массив. Иллюстрация этого способа представлена на следующем рисунке:

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

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

Практика. Хеширование и ООП-языки

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

  • a.Equals(a) == true
  • a.Equals(b) == b.Equals(a)
  • Если a.Equals(b) и b.Equals(c), то а.Equals(c)
  • Переопределяя в потомке Equals, следует переопределить и GetHashCode()
  • Если a.Equals(b) == true, то a.GetHashCode() == b.GetHashCode()
  • Значение a.GetHashCode() зависит только от внутреннего состояния объекта (его полней и свойств).

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

Заключение

В статье было дано введение в хеш-таблицы. Однако многие темы остались за «бортом», например, методология подбора хорошей хеш-функции, и идеальное хеширование, при котором поиск даже в наихудшем случае выполняется за O(1). Так же формальный анализ и доказательства некоторых приведённых утверждений вы можете найти в литературе, обозначенной ниже.

Дополнительная литература

Тема хеширования достаточно широко описана в литературе. Следующие книги я могу рекомендовать в качестве авторитетных и достоверных источников информации:

  • Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы. Построение и анализ. Издание 2-е, Вильямс, 2007 г. – Глава 11, страница 282.
  • Дональд Э. Кнут – Искусство программирования, том 2. Получисленные алгоритмы, Вильямс, 2007 г. – Глава 6.4.
  • Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы, Вильямс, 2000 г.
  • Левитин – Алгоритмы. Введение в разработку и анализ, Вильямс, 2006 г. – Глава 7.3, страница 323.

Пример реализации хеширования с цепочками можно найти в следующей книге:

  • Керниган, Пайк — Практика программирования. Издание 4-е, Вильямс, 2004 г. — Глава 2.9, страница 72.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

Илон Маск рекомендует:  contrast() в CSS

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

  • каждая из записей массива (indices [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) операций с постоянным временем.

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

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

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

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

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

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

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

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

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

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

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

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

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

Оцените реализацию хеш-таблицы

В уездном городе N проводился конкурсный отбор и было дано задание: «реализовать хеш-таблицу». Задание, вроде, несложное, но я не прошёл. Комментариев никаких дано не было, но очень хотелось бы получить обратную связь. Буду рад абсолютно любым комментариям по любому поводу, занудствовать разрешается!

4 ответа 4

Допустим, что задание было сделать хэширование именно объектов Person . Причем эти объекты являются неотъемлимой частью таблицы, что следует из рассмотрения метода push() . Именно там они создаются из аргументов метода. Более того, деструктор четко показывает на это. Тогда отставим разговоры об общности программы и наличии ссылки для списка синонимов ( next ) в Person .

Сначала все-таки о «мелочах». Константный размер таблицы мне не нравится. Пожалуй, стоило бы предусмотреть конструктор, который позволяет задавать ее размер.

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

которая хоть как-то пытается перемешивать биты ключа.

Нет методов для удаления Person (но, тогда и его деструктор, надо менять) и траверса всей таблицы.

Теперь рассмотрим реальные ошибки.

Первая — метод hash() может возращать отрицательные числа. Результат очевиден, портим память, индекс массива table ошибочный. Можно написать

Вторая — скорее логическая. В методе push() не проверяется, что такого ключа ( name в Person ) уже нет в списке синонимов.

Если предполагалась реализация «multimap», то тогда find() должен возвращать, например, список Person с одинаковым ключом. Или надо добавить метод find_next(Person) , возвращающий следующий элемент с тем же ключом.

Третья — в методе find() если заданный ключ не найден в списке синонимов, то возвращается адрес последнего Person . Очевидно, в

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL