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