Что такое хеш-таблица (hashmap)

Хеш-таблица (hashmap) — это структура данных, которая хранит пары ключ-значение и обеспечивает быстрый доступ к значению по ключу (в среднем O(1)). Работает на основе хеш-функции, которая преобразует ключ в индекс массива (бакета).

Основные моменты:

• Коллизии — когда разные ключи дают одинаковый хеш. Решаются методами:
  • Цепочки (храним список пар в одном бакете)
  • Открытая адресация (ищем следующий свободный бакет)

Пример на Python (словарь — реализация хеш-таблицы):

data = {}
data["apple"] = 5  # Ключ "apple" хешируется, значение 5 сохраняется
print(data["apple"])  # Быстрый доступ по ключу

Нюансы:

• Хеш-функция должна быть детерминированной и равномерно распределять ключи.
• При плохой хеш-функции или высокой заполненности скорость деградирует до O(n).
• В Python словарь использует открытую адресацию.