Из чего состоит хеш-таблица?

Хеш-таблица состоит из массива фиксированного размера (ведра или слоты) и хеш-функции.

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

Дополнительно может присутствовать:

• Стратегия разрешения коллизий: Механизм для обработки ситуаций, когда разные ключи генерируют один и тот же хеш-код и указывают на одну и ту же ячейку массива. Распространенные стратегии:

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