Хеш-таблица (hash table) — это структура данных, реализующая ассоциативный массив.
Принцип работы:
- Хеширование. Для каждого ключа (key) вычисляется хеш-код (hash code) с помощью хеш-функции (hash function). Хеш-код — это целое число.
- Индексирование. Хеш-код используется для определения индекса (index) в массиве (или векторе) внутренней структуры хеш-таблицы. Обычно индекс вычисляется как
hash_code % array_size, где array_size — размер массива.
- Хранение. По найденному индексу в массиве хранится связанное с ключом значение (value).
Проблемы и их решения:
- Коллизии. Различные ключи могут давать одинаковый хеш-код, и, следовательно, один и тот же индекс в массиве. Это называется коллизией.
- Методы разрешения коллизий:
- Метод цепочек (Separate Chaining): В каждой ячейке массива хранится список (список, вектор и т.п.) пар "ключ-значение". При коллизии новая пара добавляется в этот список. При поиске по индексу просматривается соответствующий список для нахождения нужного ключа.
- Метод открытой адресации (Open Addressing): При коллизии ищется другая свободная ячейка в массиве по определенному правилу (пробирование).
- Линейное пробирование (Linear Probing): Последовательно проверяются ячейки
index + 1, `ind