Хеш таблица позволяет реализовать структуру данных ассоциативный массив (словарь), со средней производительностью O(1) для операций вставки, удаления, поиска.
Ниже пример простейшей реализации хэш мапы на nodeJS:
Как это работает? Следим за руками:
- Внутри хеш мапы находится массив
- Внутри элемента массива находится указатель на первую ноду связанного списка
- Размечается память для массива указателей (например 65535 элементов)
- Реализуют хеш функцию, на вход идет ключ словаря, а на выходе она может делать что угодно, но в итоге возвращает индекс элемента массива
Как работает запись:
- На вход идет пара ключ – значение
- Хэш функция возвращает индекс по ключу
- Получаем ноду связанного списка из массива по индексу
- Проверяем соответствует ли он ключу
- Если соответствует, то заменяем значение
- Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.
- Если ноду так и не нашли, то создаем ее в конце связанного списка
Как работает поиск по ключу:
- На вход идет пара ключ – значение
- Хэш функция возвращает индекс по ключу
- Получаем ноду связанного списка из массива по индексу
- Проверяем соответствует ли он ключу
- Если соответствует, то возвращаем значение
- Если не соответствует, то переходим к следующей ноде, пока найдем либо, не найдем ноду с нужным ключом.
Зачем нужен связанный список внутри массива? Из-за возможных коллизий при вычислении хеш функции. В таком случае несколько разных пар ключ-значение будут находиться по одинаковому индексу в массиве, в таком случае осуществляется проход по связанному списку с поиском необходимого ключа.
Источники
https://ru.wikipedia.org/wiki/Хеш-таблица
https://www.youtube.com/watch?v=wg8hZxMRwcw
Исходный код
https://gitlab.com/demensdeum/datastructures