Хеширование это поиск по ключу
В хэш-таблице обработка новых индексов производится при помощи ключей. А элементы, связанные с этим ключом, сохраняются в индексе. Этот процесс называется хэшированием.
Пусть k — ключ, а h(x) — хэш-функция.
Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .
Коллизии
Когда хэш-функция генерирует один индекс для нескольких ключей, возникает конфликт (неизвестно, какое значение нужно сохранить в этом индексе). Это называется коллизией хэш-таблицы.
Есть несколько методов борьбы с коллизиями:
- Метод цепочек.
- Метод открытой адресации: линейное и квадратичное зондирование.
1. Метод цепочек
Суть этого метода проста: если хэш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка.
Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .
Псевдокод операций
2. Открытая адресация
В отличие от метода цепочек, в открытой адресации несколько элементов в одной ячейке храниться не могут. Суть этого метода заключается в том, что каждая ячейка либо содержит единственный ключ, либо NIL .
Существует несколько видов открытой адресации:
a) Линейное зондирование
Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.
h(k, i) = (h′(k) + i) mod m ,
Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть, значение i увеличивается линейно.
Проблема линейного зондирования заключается в том, что заполняется кластер соседних ячеек. Это приводит к тому, что при вставке нового элемента в хэш-таблицу необходимо проводить полный обход кластера. В результате время выполнения операций с хэш-таблицами увеличивается.
b) Квадратичное зондирование
Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:
- c1 и c2 — положительные вспомогательные константы,
- i =
c) Двойное хэширование
Если коллизия возникает после применения хэш-функции h(k) , то для поиска следующей ячейки вычисляется другая хэш-функция.
h(k, i) = (h1(k) + ih2(k)) mod m
«Хорошие» хэш-функции
«Хорошие» хэш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.
Ниже мы рассмотрим различные методы определения «качества» хэш-функций.
1. Метод деления
Если k — ключ, а m — размер хэш-таблицы, то хэш-функция h() вычисляется следующим образом:
Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть, значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.
2. Метод умножения
- kA mod 1 отделяет дробную часть kA ,
- ⌊ ⌋ округляет значение
- A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.
3. Универсальное хеширование
В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.
Это зависит от того, какую структуру данных использовать.
В односвязном списке - линейная сложность.
В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.
В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?
В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.
Идеально! Поговорим о том, как это сделать.
Кстати, на курсе «Алгоритмы и структуры данных» на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.
Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходить за константное время, как если бы мы обращались к элементу массива по индексу!
Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже «собака» на
поводкеуказателе!
Как такое возможно?
Предположим, в словаре 10.000 слов-ключей. Для их хранения мы открываем хэш-таблицу на 10.000 элементов. Возможно ли создать «волшебную» хэш-функцию-биекцию, которая каждый ключ отображала бы на индекс массива, где он должен лежать? Наверное, это возможно, если создать «небольшую» нейронную сеть и обучить её.
Если же ограничиваться простейшей хэш-функцией вида «(A * k + B) % P % N» , с возможностью подбора лишь двух коэффициентов A и В , то создать “волшебную” биекцию вряд ли удастся - коллизий не избежать. В этой формуле:
k - хэшкод уникального ключа,
P - заранее заданное простое число, большее любого возможного ключа k ,
N - размер хеш-таблицы, то есть количество всех ключей.
Идея идеального хэширования заключается в двухэтапном хэшировании.
На первом этапе находим «квартиру», а на втором этапе - «комнату», где располагается искомое значение.
Это напоминает метод разрешения коллизий методом цепочек. Но если в методе цепочек в каждой “квартире” расположен односвязный список «комнат», то в идеальном хэшировании мы в каждой квартире создадим отдельную хэш-таблицу с матрицей «комнат». Это будут «квадрокомнатные квартиры», но обо всём по порядку.
Первый этап
Минимизация количества «комнат» в «квартирах».
Поскольку список всех ключей известен заранее, то можно подобрать такие коэффициенты, чтобы максимальное количество «комнат» (коллизий) в одной «квартире» было минимальным. Достаточно несколько десятков попыток, чтобы минимизировать максимальное количество коллизий.
Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.
Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида «(A * k + B) % P % N» . Эта функция вычисляет номер «квартиры», в которой находится значение для заданного ключа. При этом минимизируется максимальное количество «комнат» (коллизий) в каждой «квартире».
Второй этап
Для размещения K элементов в одной «квартире» мы резервируем K² «комнат». Такая «квадрокомнатная квартира» позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой «квартиры» отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством «комнат».
Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:
Найти номер «квартиры» i по хэш-коду ключа k: «(A * k + B) % P % N» .
Взять коэффициенты для вычисления номера комнаты: Ai , Bi , K² .
Найти номер «комнаты» по формуле: «(Ai * k + Bi) % P % K²»
Вернуть значение из найденной «комнаты».
В любом случае (как в лучшем, так и худшем) на поиск элемента потребуется константное количество действий, которое не зависит от общего количества элементов.
Расход памяти
Может показаться, что наличие «квадрокомнатных» квартир потребует слишком много памяти для хранения нашей идеальной хэш-таблицы. Продемонстрируем, что затраты по памяти не превышают линейную сложность (троекратный расход).
Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.
Итого: для хранения “квартир” нужно N ячеек памяти, для хранения “комнат” - примерно 1.9 * N . Суммарный расход памяти: 2.9 * N = О(N) - линейный.
Заключение
Если вы уже закончили работу над крупным проектом, все настройки которого хранятся в хэш-таблице, то вы можете выписать список всех-всех-всех параметров (ключей) и создать идеальную хэш-таблицу для их хранения, чтобы увеличить скорость доступа к этим элементам.
А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.
Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:
Хеширование
Выше мы вывели ряд списковых структур, позволяющих программе-клиенту осуществлять поиск и выборку данных. В каждой такой структуре метод Find выполняет обход списка и ищет элемент данных, совпадающий с ключом. При этом эффективность поиска зависит от структуры списка. В случае последовательного списка метод Find гарантированно просматривает O(n) элементов, в то время как в случае бинарных поисковых деревьев и при бинарном поиске обеспечивается более высокая эффективность O(log 2 n).
В идеале нам хотелось бы выбирать данные за время O(1). В этом случае число необходимых сравнений не зависит от количества элементов данных. Выборка элемента осуществляется за время O(1) при использовании в качестве индекса в массиве некоторого ключа. Например, блюда из меню в закусочной в целях упрощения бухгалтерского учета обозначаются номерами. Какой-нибудь деликатес типа «бастурма, маринованная в водке» в базе данных обозначается просто №2. Владельцу закусочной остается лишь сопоставить ключ 2 с записью в списке (рисунок 25).
Мы знаем и другие примеры. Файл клиентов пункта проката видеокассет содержит семизначные номера телефонов. Номер телефона используется в качестве ключа для доступа к конкретной записи файла клиентов.
Ключи не обязательно должны быть числовыми. Например, формируемая компилятором таблица символов (symbol table) содержит все используемые в программе идентификаторы вместе с сопутствующей каждому из них информацией. Ключом для доступа к конкретной записи является сам идентификатор.
Ключи и хеш-функция
В общем случае ключи не настолько просты, как в примере с закусочной. Несмотря на то, что они обеспечивают доступ к данным, ключи, как правило, не являются непосредственными индексами в массиве записей. Например, телефонный номер может идентифицировать клиента, но вряд ли пункт проката хранит десятимиллионный массив.
В большинстве приложений ключ обеспечивает косвенную ссылку на данные. Ключ отображается во множество целых чисел посредством хеш-функции (hash function). Полученное в результате значение затем используется для доступа к данным. Давайте исследуем эту идею. Предположим, есть множество записей с целочисленными ключами. Хеш-функция HF отображает ключ в целочисленный индекс из диапазона 0. n-1. С хеш-функцией связана так называемая хеш-таблица (hash table), ячейки которой пронумерованы от 0 до n-1 и хранят сами данные или ссылки на данные.
Предположим, Key – положительное целое, а HF(Key) – значение младшей цифры числа Key. Тогда диапазон индексов равен 0-9. Например, если Key = 49, HF(Key) = HF(49) = 9. Эта хеш-функция в качестве возвращаемого значение использует остаток от деления на 10.
Часто отображение, осуществляемое хеш-функцией, является отображением «многие к одному» и приводит к коллизиям (collisions). Например, выше мы видим HF(49) = HF(29) = 9. При возникновении коллизии два или более ключа ассоциируются с одной и той же ячейкой хеш-таблицы. Поскольку два ключа не могут занимать одну и ту же ячейку в таблице, мы должны разработать стратегию разрешения коллизий.
Схемы разрешения коллизий обсуждаются после знакомства с некоторыми типами хеш-функций.
Хеш-функции
Хеш-функция должна отображать ключ в целое число из диапазона 0. n-1. При этом количество коллизий должно быть ограниченным, а вычисление самой хеш-функции – очень быстрым. Некоторые методы удовлетворяют этим требованиям.
Наиболее часто используется метод деления (division method), требующий двух шагов. Сперва ключ должен быть преобразован в целое число, а затем полученное значение вписывается в диапазон 0. n-1 с помощью оператора получения остатка. На практике метод деления используется в большинстве приложений, работающих с хешированием.
Предположим, что ключ – пятизначное число. Хеш-функция извлекает две младшие цифры. Например, если это число равно 56389, то HF(56389) = 89. Две младшие цифры являются остатком от деления на 100.
Эффективность хеш-функции зависит от того, обеспечивает ли она равномерное распределение ключей в диапазоне 0. n-1. Если две последние цифры соответствуют году рождения, то будет слишком много коллизий при идентификации подростков, играющих в юношеской бейсбольной лиге.
Другой пример – ключ-символьная строка С++. Хеш-функция отображает эту строку в целое число посредством суммирования первого и последнего символов и последующего вычисления остатка от деления на 101 (размер таблицы).
Эта хеш-функция приводит к коллизии при одинаковых первом и последнем символах строки. Например, строки «start» и «slant» будут отображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая все символы строки.
Строки «bad» и «dab» преобразуются в один и тот же индекс. Лучшие результаты дает хеш-функция, производящая перемешивание битов в символах.
В общем случае при больших n индексы имеют больший разброс. Кроме того, математическая теория утверждает, что распределение будет более равномерным, если n – простое число.
Другие методы хеширования
Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.
При мультипликативном методе (multiplicative method) используется случайное действительное число f в диапазоне от 0<f<1. Дробная часть произведения f * key лежит в диапазоне от 0 до 1. Если это произведение умножить на n (размер хеш-таблицы), то целая часть полученного произведения даст значение хеш-функции в диапазоне 0. n-1.
Разрешение коллизий
Несмотря на то, что два или более ключей могут хешироваться одинаково, они не могут занимать в хеш-таблице одну и ту же ячейку. Нам остаются два пути: либо найти для нового ключа другую позицию в таблице, либо создать для каждого значения хеш-функции отдельный список, в котором будут все ключи, отображающиеся при хешировании в это значение. Оба варианта представляют собой две классические стратегии разрешения коллизий – открытую адресацию с линейным перебором и метод цепочек . Мы проиллюстрируем на примере открытую адресацию, а сосредоточимся главным образом на втором методе, поскольку эта стратегия является доминирующей.
Открытая адресация с линейным перебором
Эта методика предполагает, что каждая ячейка таблицы помечена как незанятая. Поэтому при добавлении нового ключа всегда можно определить, занята ли данная ячейка таблицы или нет. Если да, алгоритм осуществляет перебор по кругу, пока не встретится «открытый адрес» (свободное место). Отсюда и название метода. Если размер таблицы велик относительно числа хранимых там ключей, метод работает хорошо, поскольку хеш-функция будет равномерно распределять ключи по всему диапазону и число коллизий будет минимальным. По мере того как коэффициент заполнения таблицы приближается к 1, эффективность процесса заметно падает.
Проиллюстрируем линейный перебор на примере семи записей.
Предположим, что данные имеют тип DataRecord и хранятся в 11-элементной таблице.
В качестве хеш-функции HF используется остаток от деления на 11, принимающий значения в диапазоне 0-10.
В таблице хранятся следующие данные. Каждый элемент помечен числом проб, необходимых для его размещения в таблице.
Хеширование первых пяти ключей дает пять различных индексов, по которым эти ключи запоминаются в таблице. Например, HF() = 10, и этот элемент попадает в Table[10]. Первая коллизия возникает между ключами 89 и 45, так как оба они отображаются в индекс 1.
Элемент данных идет первым в списке и занимает позицию Table[1]. При попытке записать оказывается, что место Table[1] уже занято. Тогда начинается последовательный перебор ячеек таблицы с целью нахождения свободного места. В данном случае это Table[2]. На ключе 76 эффективность алгоритма сильно падает. Этот ключ хешируется в индекс 10 – место, уже занятое. В процессе перебора осуществляется просмотр еще пяти ячеек, прежде чем будет найдено свободное место в Table[4]. Общее число проб для размещения в таблице всех элементов списка равно 13, т.е. в среднем 1,9 проб на элемент.
Метод цепочек
При другом подходе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists) .
Если таблица является массивом связанных списков, то элемент данных просто вставляется в соответствующий список в качестве нового узла. Чтобы обнаружить элемент данных, нужно применить хеш-функцию для определения нужного связанного списка и выполнить там последовательный поиск.
Проиллюстрируем метод цепочек на семи записях типа DataRecord и хеш-функции HF.
Каждый новый элемент данных вставляется в хвост соответствующего связанного списка. На рисунке 30 каждое значение данных сопровождается (в скобках) числом проб, требуемых для запоминания этого значения в таблице.
Заметьте, что если считать пробой вставку нового узла, то их общее число при вставке семи элементов равно 9, т.е. в среднем 1,3 пробы на элемент данных.
В общем случае метод цепочек быстрее открытой адресации, так как просматривает только те ключи, которые попадают в один и тот же табличный адрес. Кроме того, открытая адресация предполагает наличие таблицы фиксированного размера, в то время как в методе цепочек элементы таблицы создаются динамически, а длина списка ограничена лишь количеством памяти. Основным недостатком метода цепочек являются дополнительные затраты памяти на поля указателей. В общем случае динамическая структура метода цепочек более предпочтительна для хеширования.
Класс HashTable
В этом разделе определяется общий класс HashTable, осуществляющий хеширование методом цепочек. Этот класс образуется от базового абстрактного класса List и обеспечивает механизм хранения с очень эффективными методами доступа. Допускаются данные любого типа с тем лишь ограничением, что для этого типа данных должен быть определен оператор «==». Чтобы сравнить ключевые поля двух элементов данных, прикладная программа должна перегрузить оператор «==».
Мы также рассмотрим класс HashTableIterator, облегчающий обработку данных в хеш-таблице. Объект типа HashTableIterator находит важное применение при сортировке и доступе к данным.
Но сначала приведем листинги классов Array и LinkedList, используемых в классе HashTable. Особо пояснять мы их не будем, поскольку их обсуждение не входит в задачи этой статьи.
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто нетерпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.
| Контейнер \ операция | insert | remove | find |
|---|---|---|---|
| Array | O(N) | O(N) | O(N) |
| List | O(1) | O(1) | O(N) |
| Sorted array | O(N) | O(N) | O(logN) |
| Бинарное дерево поиска | O(logN) | O(logN) | O(logN) |
| Хеш-таблица | O(1) | O(1) | O(1) |
Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях
Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно?
Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.
Понятие хеш-таблицы
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.
Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.
Теперь стало понятно, почему же это именно хеш-таблица.
Проблема коллизии
Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии, или проблемы, когда хеш-функция выдает одинаковое натуральное число для разных элементов.
Существует несколько решений данной проблемы: метод цепочек и метод двойного хеширования. В данной статье я постараюсь рассказать о втором методе, как о более красивом и, возможно, более сложном.
Решения проблемы коллизии методом двойного хеширования
Мы будем (как несложно догадаться из названия) использовать две хеш-функции, возвращающие взаимопростые натуральные числа.
Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g.
Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).
Наконец мы объяснили все самые важные моменты, можно перейти к непосредственному написанию кода, где уже можно будет рассмотреть все оставшиеся нюансы. Ну а строгое математическое доказательство корректности использования двойного хеширования можно найти тут.
Для наглядности будем реализовывать хеш-таблицу, хранящую строки.
Начнем с определения самих хеш-функций, реализуем их методом Горнера. Важным параметром корректности хеш-функции является то, что возвращаемое значение должно быть взаимопросто с размером таблицы. Для уменьшения дублирования кода, будем использовать две структуры, ссылающиеся на реализацию самой хеш-функции.
Чтобы идти дальше, нам необходимо разобраться с проблемой: что же будет, если мы удалим элемент из таблицы? Так вот, его нужно пометить флагом deleted, но просто удалять его безвозвратно нельзя. Ведь если мы так сделаем, то при попытке найти элемент (значение хеш-функции которого совпадет с ее значением у нашего удаленного элемента) мы сразу наткнемся на пустую ячейку. А это значит, что такого элемента и не было никогда, хотя, он лежит, просто где-то дальше в массиве. Это основная сложность использования данного метода решения коллизий.
Помня о данной проблеме построим наш класс.
На данном этапе мы уже более-менее поняли, что у нас будет храниться в таблице. Переходим к реализации служебных методов.
Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.
Увеличиваем размер мы стандартно вдвое.
Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).
Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.
Но к чему слова, код все разъяснит:
Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.
Начнем с самого простого — метод Find элемент по значению.
Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.
Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.
Помимо этого в данном методе есть еще одна часть, поддерживающая правильную асимптотику. Это запоминание первого подходящего для вставки элемента (даже если он deleted). Именно туда мы вставим элемент, если в нашей хеш-таблицы нет такого же. Если ни одного deleted-элемента на нашем пути нет, мы создаем новый Node с нашим вставляемым значением.
Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math] , элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math] , а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.
Вероятность коллизий при вставке в хеш-таблицу превышает 50%Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]
'(n)[/math] — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна [math]1 - \dfrac[/math] . Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна [math]1 - \dfrac[/math] . Рассуждая аналогичным образом, получим формулу: [math]
'(n) = \left( 1 - \dfrac\right )\cdot \left( 1 - \dfrac\right )\dots\left( 1 - \dfrac\right ) = \dfrac> = \dfrac \cdot \left (len - n \right)!>[/math]
Тогда [math]
(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 -
'(n)[/math] ,
Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с прямой адресацией; в них все операции, такие как: поиск, вставка и удаление работают за [math]O(1)[/math] .
Если мы поделим число хранимых элементов на размер массива [math]H[/math] (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. load factor). От этого параметра зависит среднее время выполнения операций.
Хеширование (англ. hashing) — класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за [math]O(1)[/math] ). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицей существуют методы для борьбы с ними.
Статическое — фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов,
Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно [math]\Theta(n)[/math] , но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет [math]O(1)[/math] . А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время [math]O(1)[/math] . При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо перехешировать таблицу: увеличить размер массива [math]H[/math] и заново добавить в новую хеш-таблицу все пары.
Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
Читайте также: