Что такое hash таблица java

Хеш-таблица

Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [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]U [/math] — множество объектов (универсум).
[math]h : U \rightarrow S = \mathcal 0 \dots m — 1 \mathcal [/math] — называется хеш-функцией, где множество [math]S[/math] хранит ключи из множества [math]U[/math] .
Если [math]x \in U[/math] значит [math]h(x) \in S[/math]
Коллизия (англ. collision): [math]\exists x \neq y : h(x) = h(y)[/math]

Виды хеширования

По способу хранения:

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

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

По виду хеш-функции:

Свойства хеш-таблицы

На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно [math]\Theta(n)[/math] , но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет [math]O(1)[/math] . А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время [math]O(1)[/math] . При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо перехешировать таблицу: увеличить размер массива [math]H[/math] и заново добавить в новую хеш-таблицу все пары.

Хеширование в современных языках программирования

Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.

Java
- HashMap [1] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- HashSet [2] — реализация интерфейса множества с использованием хеш-таблицы,
- LinkedHashMap [3] — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
- unordered_map [4] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- unordered_set [5] — реализация интерфейса множества с использованием хеш-таблицы.
- dict [6] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
- set [7] — реализация интерфейса множества с использованием хеш-таблицы.
Примечания
1. ↑HashMap — Java Platform SE 7
2. ↑HashSet — Java Platform SE 7
3. ↑LinkedHashMap — Java Platform SE 7
4. ↑unordered_map — cplusplus.com
5. ↑unordered_set — cplusplus.com
6. ↑dictobject.c — https://github.com/python/cpython
7. ↑setobject.c — https://hg.python.org
Источники информации
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
- Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г. — 824 стр. — ISBN 0-201-89685-0
- Википедия — Хеш-таблица
- Дискретная математика и алгоритмы
- Хеширование
- Структуры данных
HashMap

HashMap — структура данных, одна из коллекций языка Java. Представляет собой хэш-таблицу. Так называется набор из пар «ключ-значение», где у ключей есть хэши, то есть числовые уникальные идентификаторы. Они высчитываются для каждого ключа.

Освойте профессию «Java-разработчик»

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

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

Профессия / 14 месяцев
Java-разработчик

Освойте востребованный язык

Для чего нужен HashMap

HashMap пользуются разработчики на Java. Как и все структуры, относящиеся к коллекциям, он нужен в первую очередь для хранения информации и работы с ней. HashMap быстро работает, и большинство операций в нем выполняется за фиксированное время — это происходит благодаря оптимизированному доступу к данным. Как и практически все структуры из Collections Framework, он динамический, то есть его размер не фиксирован — туда можно добавить практически любое количество объектов.

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

Как устроены хэш-таблицы

HashMap — структура из пар «ключ-значение». Внутри это динамический массив ключей. Каждый элемент массива — своеобразная «корзинка», которая хранит связанный список со значением. О том, что собой представляет каждая из этих сущностей, можно почитать в статьях про ArrayList и коллекции.

Но HashMap используют для хранения пар — на каждый ключ приходится только одно значение. То есть связанный список будет состоять из одного элемента, а ссылаться этот элемент будет на null — специальное «пустое» значение. Если бы в такой структуре значений было несколько, первое ссылалось бы на второе и так далее — так устроен связанный список.

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

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

Станьте Java-разработчиком
и создавайте сложные сервисы
на востребованном языке

Реализация и свойства HashMap

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

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

Коллизии и их предотвращение

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

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

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

Отличие от перезаписи

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

Java-разработчик

Java уже 20 лет в мировом топе языков программирования. На нем создают сложные финансовые сервисы, стриминги и маркетплейсы. Освойте технологии, которые нужны для backend-разработки, за 14 месяцев.

Хеш-таблицы

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

Пусть k — ключ, а h(x) — хеш-функция.

Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .

Коллизии

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

Есть несколько методов борьбы с коллизиями:
- метод цепочек;
- метод открытой адресации: линейное и квадратичное зондирование.
1. Метод цепочек

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

Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .

Псевдокод операций
```
chainedHashSearch(T, k) return T[h(k)] chainedHashInsert(T, x) T[h(x.key)] = x chainedHashDelete(T, x) T[h(x.key)] = NIL 
```
2. Открытая адресация

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

Существует несколько видов открытой адресации:

a) Линейное зондирование

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

h(k, i) = (h′(k) + i) mod m ,
- i =
- h'(k) — новая хеш-функция
Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть значение i увеличивается линейно.

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

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:
- c₁ и c₂ — положительные вспомогательные константы,
- 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-биты низшего порядка.
```
если m = 22, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 01 если m = 23, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 001 если m = 24, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 0001 если m = 2p, тогда h(k) = p биты порядком ниже, чем m
```
2. Метод умножения
- kA mod 1 отделяет дробную часть kA;
- ⌊ ⌋ округляет значение;
- A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.
3. Универсальное хеширование

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

Где применяются
- Когда необходима постоянная скорость поиска и вставки.
- В криптографических приложениях.
- Когда необходима индексация данных.
Примеры реализации хеш-таблиц в Python, Java, Си и C++

Python
```
# Реализация хеш-таблицы в Python hashTable = [[],] * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable[index] = [key, data] def removeData(key): index = hashFunction(key) hashTable[index] = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
```
Java
```
// Реализация хеш-таблицы в Java import java.util.*; class HashTable < public static void main(String args[]) < Hashtableht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); > > 
```
Cи
```
// Реализация хеш-таблицы в Cи #include #include struct set < int key; int data; >; struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) < return (key % capacity); >int checkPrime(int n) < int i; if (n == 1 || n == 0) < return 0; >for (i = 2; i < n / 2; i++) < if (n % i == 0) < return 0; >> return 1; > int getPrime(int n) < if (n % 2 == 0) < n++; >while (!checkPrime(n)) < n += 2; >return n; > void init_array() < capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) < array[i].key = 0; array[i].data = 0; >> void insert(int key, int data) < int index = hashFunction(key); if (array[index].data == 0) < array[index].key = key; array[index].data = data; size++; printf("\n Ключ (%d) вставлен \n", key); >else if (array[index].key == key) < array[index].data = data; >else < printf("\n Возникла коллизия \n"); >> void remove_element(int key) < int index = hashFunction(key); if (array[index].data == 0) < printf("\n Данного ключа не существует \n"); >else < array[index].key = 0; array[index].data = 0; size--; printf("\n Ключ (%d) удален \n", key); >> void display() < int i; for (i = 0; i < capacity; i++) < if (array[i].data == 0) < printf("\n array[%d]: / ", i); >else < printf("\n Ключ: %d array[%d]: %d \t", array[i].key, i, array[i].data); >> > int size_of_hashtable() < return size; >int main() < int choice, key, data, n; int c = 0; init_array(); do < printf("1.Вставить элемент в хэш-таблицу" "\n2.Удалить элемент из хэш-таблицы" "\n3.Узнать размер хэш-таблицы" "\n4.Вывести хэш-таблицу" "\n\n Пожалуйста, выберите нужный вариант: "); scanf("%d", &choice); switch (choice) < case 1: printf("Введите ключ -:\t"); scanf("%d", &key); printf("Введите данные-:\t"); scanf("%d", &data); insert(key, data); break; case 2: printf("Введите ключ, который хотите удалить-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Размер хеш-таблицы-:%d\n", n); break; case 4: display(); break; default: printf("Неверно введены данные\n"); >printf("\nПродолжить? (Нажмите 1, если да): "); scanf("%d", &c); > while (c == 1); > 
```
C++
```
// Реализация хеш-таблицы в C++ #include #include using namespace std; class HashTable < int capacity; list*table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) < int i; if (n == 1 || n == 0) < return 0; >for (i = 2; i < n / 2; i++) < if (n % i == 0) < return 0; >> return 1; > int getPrime(int n) < if (n % 2 == 0) < n++; >while (!checkPrime(n)) < n += 2; >return n; > int hashFunction(int key) < return (key % capacity); >void displayHash(); >; HashTable::HashTable(int c) < int size = getPrime(c); this->capacity = size; table = new list[capacity]; > void HashTable::insertItem(int key, int data) < int index = hashFunction(key); table[index].push_back(data); >void HashTable::deleteItem(int key) < int index = hashFunction(key); list::iterator i; for (i = table[index].begin(); i != table[index].end(); i++) < if (*i == key) break; >if (i != table[index].end()) table[index].erase(i); > void HashTable::displayHash() < for (int i = 0; i < capacity; i++) < cout " > int main() < int key[] = ; int data[] = ; int size = sizeof(key) / sizeof(key[0]); HashTable h(size); for (int i = 0; i
```
СodeСhick.io - простой и эффективный способ изучения программирования.

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

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

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

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

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

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

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

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

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

Ниже приведены код хеш-функции на основе первой буквы в строке
```
int hash_function (char * key)
```
Коллизии (столкновения)

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

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

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

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

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

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

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

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

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

Описание структуры узла префиксного дерева — ниже. Заметьте, мы фактически не сохраняем слова в trie, мы просто сохраняем последовательность указателей и логическое значение.
```
typedef struct node < // Маркер конца слова bool is_word; // Указатели на другие элементы struct node * children [27]; >Node;
```
Пример работы с префиксным деревом

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

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

Мы начнем поиск в корневом узле. Берём первую букву нашего ключа «b» и ищем соответствующее место в нашем дочернем массиве. Мы рассмотрим второй индекс — индекс 1 — для «b». В общем случае, если у нас есть алфавитный символ c, мы можем определить соответствие в дочернем массиве, используя такую формулу:
```
int index = tolower (c) - 'a';
```
В этом случае указатель в нашем дочернем массиве с индексом 1 не является NULL, поэтому мы продолжим поиск ключа «bat». Если мы однажды наткнёмся на указатель NULL в правильном месте дочернего массива, тогда, смотря на ключ, мы должны были бы сказать, что мы ничего не смогли найти для этого ключа.

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

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

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

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

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

Давайте рассмотрим, как можно вставить элемент в префиксное дерево. В некотором смысле процесс вставки похож на процесс поиска.

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

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

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

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

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

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

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

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

Читать:
Как отличить впускной распредвал от выпускного ваз 2112 16 клапанов