Хеш-таблицы
Хеш-таблица — это структура данных для хранения пар ключей и их значений. По сути она представляет собой массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Важное свойство хеш-таблицы: поиск, вставка и удаление элементов из таблицы выполняются за фиксированное время, то есть О(1), то есть они нужны тогда, когда максимально важна скорость этих операций.
![Хеш-таблицы, деревья и префиксные деревья - 1](https://cdn.javarush.com/images/article/e949215d-38e5-41cb-9cf6-6e345da86b5b/original.png)
В примере на картинке позиция каждого слова в хеш-таблице зависит от порядкового номера первой буквы этого слова в английском алфавите.
Хеш-функция — это функция, которая принимает в качестве аргумента какой-то элемент (который нужно вставить в хеш-таблицу), а в результате выдает позицию заданного элемента в хеш-таблицы.
![Хеш-таблицы, деревья и префиксные деревья - 2](https://cdn.javarush.com/images/article/d4055fef-b5a3-490b-83ee-dd299520bcfe/original.png)
По сути она сопоставляет ключи индексам массива. Например, на картинке выше мы видим, что хеш-функция сопоставила ключ ‘banana’ с индексом 1.
Но что происходит под капотом?
Хеш-функция принимает ключ на вход и вычисляет индекс массива, исходя из внутренних свойств этого ключа.
Сначала вам нужно использовать хеш-функцию, чтобы определить, где в хеш-таблице хранится данный ключ. Затем нужно будет использовать ту же самую хеш-функцию, чтобы определить, где в хеш-таблице искать данный ключ. По этой причине важно, чтобы хеш-функция вела себя последовательно и выводила один и тот же индекс для одинаковых входных данных.
Примеры хеш-функций: порядковый номер первой буквы слова в алфавите, остаток от деления на 13 и тому подобное.
Ниже приведены код хеш-функции на основе первой буквы в строке
int hash_function (char * key)
{
int hash = toupper (key [0]) - 'A';
return hash% SIZE;
}
Коллизии (столкновения)
Ситуация, когда для разных ключей получается одно и то же хеш-значение, называется коллизией или столкновением. Например, в изображенную ранее таблицу на основе первых символов строки мы попробуем добавить новое слово berry.
![Хеш-таблицы, деревья и префиксные деревья - 3](https://cdn.javarush.com/images/article/403acea3-a684-4b23-9c4b-324cf89510b7/original.png)
Индекс Berry ссылается на 1, как и банан. Это пример столкновения, результат хеширования двух ключей к одному индексу. Даже если ваш хеш-табличка больше, чем ваш набор данных, и вы выбрали хорошую хеш-функцию, вам нужен план борьбы со столкновениями, если и когда они возникнут.
Полученное новое значение также нужно куда-то записать, и для этого нужно определить, куда именно оно будет записано. Это называется решением коллизии.
Двумя распространенными методами борьбы с коллизиями являются линейное зондирование и метод цепочек.
Линейное зондирование заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция.
![Хеш-таблицы, деревья и префиксные деревья - 4](https://cdn.javarush.com/images/article/9e4d0507-99cc-499a-81a3-2bf9438e70ae/original.png)
При методе цепочек, каждая ячейка хеш-таблицы — это список значений. При возникновении коллизии, новое значение просто добавляется в список в ту же ячейку таблицы.
![Хеш-таблицы, деревья и префиксные деревья - 5](https://cdn.javarush.com/images/article/2837acaf-9ad2-4ce1-86e0-271f44a27add/original.png)
Префиксное дерево
Префиксное дерево (trie) — структура данных, в которой путь от корня дерева к листу (последнему элементу) дерева определяет строку.
Слово «trie» происходит от слова «retrieval» (извлечение), но обычно произносится как «try». Для наших целей узлы в trie являются массивами. Мы можем использовать trie для хранения словаря слов, как показано на этой диаграмме.
![Хеш-таблицы, деревья и префиксные деревья - 6](https://cdn.javarush.com/images/article/f3e18606-7fad-4347-9dc8-44a121dcb60a/original.png)
В этом trie каждый индекс в массиве обозначает букву алфавита. Каждый из этих индексов также указывает на другой массив букв. Сверху мы сохраняем имена известных ученых, например. Менделя, Менделеева, Павлова, Пастера и Тьюринга. Символ Δ обозначает конец имени. Мы должны следить за тем, где заканчиваются слова, так что если одно слово действительно содержит другое слово (например, Менделеев и Мендель), мы знаем, что оба слова существуют. В коде символ Δ может быть логическим флагом в каждом узле.
Таким образом, при прохождении дерева сверху вниз формируются слова.
Описание структуры узла префиксного дерева — ниже. Заметьте, мы фактически не сохраняем слова в trie, мы просто сохраняем последовательность указателей и логическое значение.
typedef struct node
{
// Маркер конца слова
bool is_word;
// Указатели на другие элементы
struct node * children [27];
} Node;
Пример работы с префиксным деревом
Есть следующего вида префиксальное дерево, в котором есть слова bat
и zoom
:
![Хеш-таблицы, деревья и префиксные деревья - 7](https://cdn.javarush.com/images/article/352cd423-2351-4596-b002-484bdb67a222/original.png)
Давайте рассмотрим пример поиска ключа «bat» в этом trie. Переходя по последовательным ссылкам сверху вниз, пока не встретим маркер конца слова, получим слово bat:
![Хеш-таблицы, деревья и префиксные деревья - 8](https://cdn.javarush.com/images/article/1e0f8679-d299-4971-9c08-c190a7ec6797/original.png)
Мы начнем поиск в корневом узле. Берём первую букву нашего ключа «b» и ищем соответствующее место в нашем дочернем массиве. Мы рассмотрим второй индекс — индекс 1 — для «b». В общем случае, если у нас есть алфавитный символ c, мы можем определить соответствие в дочернем массиве, используя такую формулу:
int index = tolower (c) - 'a';
В этом случае указатель в нашем дочернем массиве с индексом 1 не является NULL, поэтому мы продолжим поиск ключа «bat». Если мы однажды наткнёмся на указатель NULL в правильном месте дочернего массива, тогда, смотря на ключ, мы должны были бы сказать, что мы ничего не смогли найти для этого ключа.
![Хеш-таблицы, деревья и префиксные деревья - 9](https://cdn.javarush.com/images/article/42910955-1b67-4a41-bc74-59ddf9014728/original.png)
Теперь мы возьмем вторую букву нашего ключа «a» и продолжим следовать по указателям, пока не дойдем до конца нашего ключа.
![Хеш-таблицы, деревья и префиксные деревья - 10](https://cdn.javarush.com/images/article/35ab4fe2-0663-4e9d-922d-59140db7b55b/original.png)
Теперь (сюрприз!) мы возьмем третью букву нашего ключа, «t», и продолжим идти по указателям, пока не дойдем до конца нашего ключа.
![Хеш-таблицы, деревья и префиксные деревья - 11](https://cdn.javarush.com/images/article/38170be6-40c6-4b59-b644-c3c54fbc1c0f/original.png)
Если мы дойдем до конца ключа, и не попадём в «тупик» (NULL-указатель), как здесь, то нам остается только проверить еще одну вещь: был ли этот ключ фактически сохранен в trie? На нашей диаграмме это обозначается галочкой, означающей, что bool is_word = true
.
![Хеш-таблицы, деревья и префиксные деревья - 12](https://cdn.javarush.com/images/article/b011f6d4-2ff3-46cd-9fac-26f3ce465680/original.png)
Обратите внимание, на то, что ключ «zoo» отсутствует в словаре, хотя мы смогли дойти до конца этого ключа, не попав в тупик.
![Хеш-таблицы, деревья и префиксные деревья - 13](https://cdn.javarush.com/images/article/5e4634ea-8721-42be-ad95-53ca53073069/original.png)
Точно так же, если бы мы попытались найти ключ «bath», индекс массива массива от второго до последнего узла, соответствующий букве Н, содержал бы указатель NULL, поэтому «bath» отсутствует в словаре.
Давайте рассмотрим, как можно вставить элемент в префиксное дерево. В некотором смысле процесс вставки похож на процесс поиска.
Для того чтобы вставить слово zoo в массив, необходимо начать с корневого узла, следуя по указателям, соответствующим буквам нашего ключа, проходим по списку и устанавливаем маркер:
![Хеш-таблицы, деревья и префиксные деревья - 14](https://cdn.javarush.com/images/article/0c20d457-225a-45e4-9792-09c95bc7f12c/original.png)
К счастью, мы можем следить за указателями до конца ключа.
![Хеш-таблицы, деревья и префиксные деревья - 15](https://cdn.javarush.com/images/article/c5d480a1-47ae-4a7d-876c-0e3e07742485/original.png)
![Хеш-таблицы, деревья и префиксные деревья - 16](https://cdn.javarush.com/images/article/b810064a-c291-40eb-806b-25fafb8fe5a3/original.png)
Поскольку «zoo» является префиксом слова «zoom», которое хранится в нашем словаре, нам не нужно выделять новые узлы. Мы можем просто установить is_word в true на соответствующем узле.
![Хеш-таблицы, деревья и префиксные деревья - 17](https://cdn.javarush.com/images/article/480ae8c9-8b23-4e52-a437-42ca6a617e87/original.png)
А если бы мы захотели добавить в дерево слово bath, то, пройдя по всем указателям, мы бы зашли в тупик прежде, чем добрались до конца ключа.
![Хеш-таблицы, деревья и префиксные деревья - 18](https://cdn.javarush.com/images/article/f4a11687-100d-4d7f-b90d-ad12d6e82978/original.png)
Поэтому нам нужно определить один новый узел для каждой оставшейся буквы нашего ключа.
![Хеш-таблицы, деревья и префиксные деревья - 19](https://cdn.javarush.com/images/article/30fb41af-d66f-405c-976e-18374fbb8790/original.png)
Затем нам нужно будет сделать индекс h предыдущего узла ссылкой на этот новый узел. То есть в последнем элементе слова bat создаем ссылку, указывающую на букву h:
![Хеш-таблицы, деревья и префиксные деревья - 20](https://cdn.javarush.com/images/article/ff3885da-bf5f-41e2-b55e-891067a30eb1/original.png)
Наконец, мы устанавливаем значение true для is_word bool нового узла. Если предположить, что длина ключа ограничена фиксированной константой, ясно, что и поиск, и вставка выполняются за фиксированное время. Обратите внимание, что количество элементов, хранящихся в trie, не влияет на время поиска или вставки, влияние оказывает только длина ключа. В отличие от этого добавление записей в хеш-таблицу имеет тенденцию замедления поиска в будущем.
![Хеш-таблицы, деревья и префиксные деревья - 21](https://cdn.javarush.com/images/article/1a48f8f2-acce-4531-8363-c65eb672b3d0/original.png)
Естественно, благоприятная асимптотическая сложность привлекает, однако не стоит обольщаться, на практике всё не так радужно. Мы также должны учитывать, что для хранения слова в trie нам нужно, в худшем случае, несколько узлов, пропорциональных длине самого слова. Попытки, как правило, требуют много места, и в этом отличие этой структуры данных от, скажем, хеш-таблиц, где нам нужен только один новый узел для хранения пары ключ-значение.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ