Хеш-таблицы

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

Хеш-таблицы, деревья и префиксные деревья - 1

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

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

Хеш-таблицы, деревья и префиксные деревья - 2

По сути она сопоставляет ключи индексам массива. Например, на картинке выше мы видим, что хеш-функция сопоставила ключ ‘banana’ с индексом 1.

Но что происходит под капотом?

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

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

Примеры хеш-функций: порядковый номер первой буквы слова в алфавите, остаток от деления на 13 и тому подобное.

Ниже приведены код хеш-функции на основе первой буквы в строке

int hash_function (char * key)
{
  int hash = toupper (key [0]) - 'A';
  return hash% SIZE;
}

Коллизии (столкновения)

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

Хеш-таблицы, деревья и префиксные деревья - 3

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

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

Линейное зондирование заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция.

Хеш-таблицы, деревья и префиксные деревья - 4

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

Хеш-таблицы, деревья и префиксные деревья - 5

Префиксное дерево

Префиксное дерево (trie) — структура данных, в которой путь от корня дерева к листу (последнему элементу) дерева определяет строку.
Слово «trie» происходит от слова «retrieval» (извлечение), но обычно произносится как «try». Для наших целей узлы в trie являются массивами. Мы можем использовать trie для хранения словаря слов, как показано на этой диаграмме.

Хеш-таблицы, деревья и префиксные деревья - 6

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

Таким образом, при прохождении дерева сверху вниз формируются слова.

Описание структуры узла префиксного дерева — ниже. Заметьте, мы фактически не сохраняем слова в trie, мы просто сохраняем последовательность указателей и логическое значение.

typedef struct node
{
  // Маркер конца слова
  bool is_word;
  // Указатели на другие элементы
  struct node * children [27];
} Node;

Пример работы с префиксным деревом

Есть следующего вида префиксальное дерево, в котором есть слова bat и zoom:

Хеш-таблицы, деревья и префиксные деревья - 7

Давайте рассмотрим пример поиска ключа «bat» в этом trie. Переходя по последовательным ссылкам сверху вниз, пока не встретим маркер конца слова, получим слово bat:

Хеш-таблицы, деревья и префиксные деревья - 8

Мы начнем поиск в корневом узле. Берём первую букву нашего ключа «b» и ищем соответствующее место в нашем дочернем массиве. Мы рассмотрим второй индекс — индекс 1 — для «b». В общем случае, если у нас есть алфавитный символ c, мы можем определить соответствие в дочернем массиве, используя такую формулу:

int index = tolower (c) - 'a';

В этом случае указатель в нашем дочернем массиве с индексом 1 не является NULL, поэтому мы продолжим поиск ключа «bat». Если мы однажды наткнёмся на указатель NULL в правильном месте дочернего массива, тогда, смотря на ключ, мы должны были бы сказать, что мы ничего не смогли найти для этого ключа.

Хеш-таблицы, деревья и префиксные деревья - 9

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

Хеш-таблицы, деревья и префиксные деревья - 10

Теперь (сюрприз!) мы возьмем третью букву нашего ключа, «t», и продолжим идти по указателям, пока не дойдем до конца нашего ключа.

Хеш-таблицы, деревья и префиксные деревья - 11

Если мы дойдем до конца ключа, и не попадём в «тупик» (NULL-указатель), как здесь, то нам остается только проверить еще одну вещь: был ли этот ключ фактически сохранен в trie? На нашей диаграмме это обозначается галочкой, означающей, что bool is_word = true.

Хеш-таблицы, деревья и префиксные деревья - 12

Обратите внимание, на то, что ключ «zoo» отсутствует в словаре, хотя мы смогли дойти до конца этого ключа, не попав в тупик.

Хеш-таблицы, деревья и префиксные деревья - 13

Точно так же, если бы мы попытались найти ключ «bath», индекс массива массива от второго до последнего узла, соответствующий букве Н, содержал бы указатель NULL, поэтому «bath» отсутствует в словаре.

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

Хеш-таблицы, деревья и префиксные деревья - 14

К счастью, мы можем следить за указателями до конца ключа.

Хеш-таблицы, деревья и префиксные деревья - 15
Хеш-таблицы, деревья и префиксные деревья - 16

Поскольку «zoo» является префиксом слова «zoom», которое хранится в нашем словаре, нам не нужно выделять новые узлы. Мы можем просто установить is_word в true на соответствующем узле.

Хеш-таблицы, деревья и префиксные деревья - 17

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

Хеш-таблицы, деревья и префиксные деревья - 18

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

Хеш-таблицы, деревья и префиксные деревья - 19

Затем нам нужно будет сделать индекс h предыдущего узла ссылкой на этот новый узел. То есть в последнем элементе слова bat создаем ссылку, указывающую на букву h:

Хеш-таблицы, деревья и префиксные деревья - 20

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

Хеш-таблицы, деревья и префиксные деревья - 21

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