Хеш-таблица (Hash table)
Хеш-таблица — структура данных состоящая из хеш-функции и массива для хранения данных.
Хеш-функция должна удовлетворять следующим условиям:
- Для одной входной строки возвращать одно значение
- Для разных входных строк возвращать разные значения
- Кол-во выходных значений должно быть не больше размера массива
Чем равномернее хеш-функция распределяет ключи тем выше эффективность хеш-таблицы, так как от этого зависит наличие коллизий.
Коллизии
Мощность множества входных значений больше чем мощность множества в можно хранить результаты. Из-за этого какие-то значения придется хранить в одной ячейке массива.
Варианты решения:
- Использовать связанный список как значение массива.
Коэффициент заполнения — количество элементов в хеш-таблице делённое на общее количество элементов. Коэффициент может больше 1, это значит в одной ячейке уже больше одного элемента. Полезно увеличение размера когда коэффициент приближается к 0.7.
Способы использования хеш-таблиц
- Отображение одних объектов на другие (телефонная книга)
- Исключение дубликатов
- Кеширование (отдельная страница)
Производительность
Поиск, вставка и удаления в среднем случае , а в худшем случае
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 5. Хеш-таблицы