Хеш-таблица (hashmap) — это структура данных, которая хранит пары ключ-значение и обеспечивает быстрый доступ к значению по ключу (в среднем O(1)). Работает на основе хеш-функции, которая преобразует ключ в индекс массива (бакета). **Основные моменты:** - **Коллизии** — когда разные ключи дают одинаковый хеш. Решаются методами: - **Цепочки** (храним список пар в одном бакете) - **Открытая адресация** (ищем следующий свободный бакет) **Пример на Python (словарь — реализация хеш-таблицы):** ``` data = {} data["apple"] = 5 # Ключ "apple" хешируется, значение 5 сохраняется print(data["apple"]) # Быстрый доступ по ключу ``` **Нюансы:** - Хеш-функция должна быть детерминированной и равномерно распределять ключи. - При плохой хеш-функции или высокой заполненности скорость деградирует до O(n). - В Python словарь использует открытую адресацию.