Хеш-таблица (хеш-мап) — это структура данных, реализующая ассоциативный массив, которая отображает ключи на значения.
Основной принцип работы:
- Хеширование: Для каждого ключа вычисляется хеш-код — числовое значение фиксированного размера с помощью хеш-функции. Хорошая хеш-функция распределяет хеш-коды равномерно по всему диапазону выходов.
- Индексирование: Вычисленный хеш-код используется для определения индекса (позиции) в массиве, где будет храниться соответствующее значение. Часто хеш-код по модулю размера массива (
hash(key) % array_size) дает итоговый индекс.
- Хранение: В массиве по рассчитанному индексу хранится пара (ключ, значение).
- Поиск: Для нахождения значения по ключу, снова вычисляется хеш-код ключа, определяется индекс, и по этому индексу извлекается значение.
- Коллизии: Возникают, когда разные ключи имеют одинаковый хеш-код. Существуют различные методы для разрешения коллизий:
- Метод цепочек (Separate Chaining): По каждому индексу массива хранится список (или другая структура данных), содержащий все пары (ключ, значение), хеш-коды которых п