Как устроена HashMap

HashMap (в Python — dict) — это структура данных, реализующая ассоциативный массив через хеш-таблицу.

Основные принципы:

1. Хеширование ключей — каждый ключ преобразуется в хеш (целое число) через hash().
2. Разрешение коллизий — при совпадении хешей используется метод открытой адресации или цепочек. В Python (CPython) применяется открытая адресация.
3. Динамическое расширение — при заполнении таблицы на ~2/3 она увеличивается, чтобы сохранить эффективность вставки (O(1) в среднем).

Пример:

d = {}
d["key"] = "value"  # Хеш "key" вычисляется, значение сохраняется в таблицу.
print(d["key"])     # Быстрый доступ по хешу.

Нюансы:

• Ключи должны быть хешируемыми (неизменяемыми типы: str, int, tuple).
• Порядок ключей в Python 3.7+ сохраняется (реализация деталей CPython).
• Коллизии замедляют операции, но хорошая хеш-функция минимизирует их.