Хеш-таблица состоит из массива фиксированного размера (ведра или слоты) и хеш-функции.
-
Массив (Buckets/Slots): Представляет собой последовательность ячеек, в которых хранятся пары "ключ-значение". Размер массива определяет количество возможных мест для хранения элементов.
-
Хеш-функция: Преобразует ключ в целочисленное значение (хеш-код), которое используется для определения индекса ячейки в массиве (bucket), где будет храниться или откуда будет извлечено соответствующее значение.
Дополнительно может присутствовать:
- Стратегия разрешения коллизий: Механизм для обработки ситуаций, когда разные ключи генерируют один и тот же хеш-код и указывают на одну и ту же ячейку массива. Распространенные стратегии:
- Метод цепочек (Separate Chaining): Каждая ячейка массива хранит указатель на связный список (или другой структуру данных), содержащий все пары "ключ-значение", хеш-коды которых указывают на эту ячейку.
- Метод открытой адресации (Open Addressing): При коллизии осуществляется поиск свободной ячейки в самом массиве по определенному правилу (например, линейное или квадратичное пробирование).