Как работает хеш-таблица (HashMap) в Python

В Python хеш-таблица реализована через встроенный тип dict. Она использует хеш-функцию для преобразования ключа в целочисленный хеш, который определяет индекс в массиве (бакете), где хранится значение.

Ключевые моменты:

• Ключи должны быть хешируемыми (неизменяемыми типами, например, int, str, tuple).
• При коллизиях (одинаковый хеш для разных ключей) используется метод цепочек или открытая адресация.
• В среднем операции get, set, del работают за O(1), но в худшем случае — O(n).

Пример:

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

Нюансы:

• Размер таблицы динамически меняется при добавлении элементов.
• Порядок ключей сохраняется только в Python 3.7+ (реализация стала компактнее).