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

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

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

Основной принцип работы

Хеш-таблица использует хеш-функцию для преобразования ключа в индекс массива:

# Упрощенный пример
hash(key) -> индекс -> значение в массиве

Как Python реализует dict

# Создание словаря (хеш-таблицы)
user = {
    "name": "Alice",
    "age": 30,
    "email": "alice@example.com"
}

# Доступ за O(1)
print(user["name"])  # Alice

# Добавление за O(1)
user["city"] = "NYC"

# Удаление за O(1)
del user["age"]

Внутренняя структура

Когда вы добавляете элемент в dict:

1. Вычисляется хеш ключа: hash(key)
2. Вычисляется индекс: index = hash(key) % table_size
3. Значение сохраняется в массиве по этому индексу

# Пример хеширования
key = "name"
hash_value = hash(key)  # Некоторое число
index = hash_value % 8  # Если размер таблицы = 8
# Значение сохраняется в массиве[index]

Коллизии (Collision Handling)

Когда два разных ключа имеют одинаковый индекс, происходит коллизия. Python использует открытую адресацию (linear probing, perturbed hash) для разрешения коллизий.

# Коллизия
d = {}
d["key1"] = "value1"  # hash("key1") % size = 2
d["key2"] = "value2"  # hash("key2") % size = 2 (коллизия!)

# Python найдет другой индекс для key2
# При поиске он будет проверять соседние индексы

Динамическое расширение (Resizing)

Когда словарь заполняется (load factor > порога), он автоматически расширяется:

# Python отслеживает размер словаря
d = {}
# Изначальный размер: 8
for i in range(100):
    d[f"key{i}"] = i

# При добавлении элементов размер растет: 8 -> 32 -> 256 -> ...
# Процесс: создается новый большой массив, все элементы перехешируются

import sys
print(sys.getsizeof(d))  # Размер словаря в байтах

Требования к ключам

Ключи должны быть hashable (неизменяемыми):

# Правильно: hashable ключи
d = {}
d[1] = "one"                    # int
d["key"] = "value"              # str
d[(1, 2)] = "tuple"             # tuple
d[frozenset([1, 2])] = "frozen" # frozenset

# Неправильно: unhashable ключи
# d[[1, 2]] = "list"                  # TypeError: unhashable type: 'list'
# d[{"key": "value"}] = "dict"        # TypeError: unhashable type: 'dict'

Пользовательский класс как ключ

class User:
    def __init__(self, id):
        self.id = id
    
    def __hash__(self):
        return hash(self.id)
    
    def __eq__(self, other):
        return isinstance(other, User) and self.id == other.id

user1 = User(1)
user2 = User(1)

d = {}
d[user1] = "data"
print(d[user2])  # "data" — находит по хешу и равенству

Производительность

# Средняя случай: O(1)
d = {i: i**2 for i in range(1000000)}
value = d[500000]  # Очень быстро

# Худший случай: O(n) (редко, при плохой хеш-функции)
# Но Python использует хорошую хеш-функцию, поэтому это редко

Порядок элементов (Python 3.7+)

d = {}
d["z"] = 1
d["a"] = 2
d["m"] = 3

# Python 3.7+: порядок сохраняется (insertion order)
for key in d:
    print(key)  # z, a, m (в порядке добавления)

Set — хеш-таблица без значений

s = {"apple", "banana", "cherry"}
# Set использует ту же хеш-таблицу, но без значений
# Операции: добавление O(1), удаление O(1), поиск O(1)

s.add("date")       # O(1)
s.remove("apple")   # O(1)
"banana" in s       # O(1)

Сравнение временных сложностей

Практическое применение

# Подсчет частоты слов
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
frequency = {}

for word in words:
    frequency[word] = frequency.get(word, 0) + 1

print(frequency)  # {'apple': 3, 'banana': 2, 'cherry': 1}

# Кеширование
cache = {}

def expensive_function(n):
    if n in cache:
        return cache[n]  # O(1) lookup
    
    result = n ** 2
    cache[n] = result  # O(1) сохранение
    return result

Заключение

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