Что произойдёт при коллизии хэшей в словаре Python?

Коллизии хэшей в словаре Python

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

Как работает хэширование в словаре

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

d = {}
d["key1"] = "value1"

Python выполняет следующие шаги:

1. Вычисляет хэш ключа: hash("key1") → какое-то число
2. Преобразует хэш в индекс в хэш-таблице
3. Проверяет, занята ли позиция
4. Если свободна — сохраняет пару (ключ, значение)
5. Если занята — переходит к следующей позиции (открытая адресация)

Что происходит при коллизии

Если два ключа имеют один и тот же хэш:

class Key:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 42  # Плохой хэш — все ключи имеют одинаковый хэш
    
    def __eq__(self, other):
        return isinstance(other, Key) and self.value == other.value

key1 = Key(1)
key2 = Key(2)
key3 = Key(3)

d = {}
d[key1] = "value1"
d[key2] = "value2"
d[key3] = "value3"

print(len(d))  # 3 — все три ключа сохранены!
print(d[key1])  # value1

Потому что Python не только смотрит на хэш, но и проверяет равенство ключей через __eq__(). Даже если хэши совпадают, ключи разные (key1 != key2), поэтому они оба сохраняются в словаре.

Механизм разрешения коллизий

Python 3.6+ использует компактное представление словарей, но принцип открытой адресации остаётся:

# Внутренне словарь выглядит примерно так:
# Хэш-таблица:
# [0]:   пусто
# [1]:   пусто
# [42]:  (key1, value1)  ← ключ с хэшем 42
# [43]:  (key2, value2)  ← коллизия, переместили на следующую позицию
# [44]:  (key3, value3)  ← ещё одна коллизия
# [45]:  пусто

При поиске d[key2]:

1. Вычисляет hash(key2) = 42
2. Проверяет позицию [42]: там (key1, value1)
3. Проверяет key1 == key2 → False
4. Переходит к позиции [43]: там (key2, value2)
5. Проверяет key2 == key2 → True
6. Возвращает value2

Практический пример

# Коллизии на практике

class BadHash:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return 1  # Все экземпляры имеют одинаковый хэш
    
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.name == other.name
    
    def __repr__(self):
        return f"BadHash({self.name})"

# Создаём словарь с коллизиями
d = {}
for i in range(5):
    key = BadHash(f"key{i}")
    d[key] = f"value{i}"

print(len(d))  # 5 — все элементы успешно сохранены
print(d[BadHash("key2")])  # value2

# Ищем элемент
result_key = BadHash("key2")
if result_key in d:
    print(f"Найден: {d[result_key]}")

Производительность при коллизиях

Когда много коллизий, производительность словаря деградирует:

import timeit

class GoodHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return hash(self.value)  # Хороший хэш
    
    def __eq__(self, other):
        return isinstance(other, GoodHash) and self.value == other.value

class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 1  # Все имеют одинаковый хэш
    
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.value == other.value

# Заполнение словаря с хорошими хэшами: O(1) в среднем
good_dict = {GoodHash(i): i for i in range(10000)}

# Заполнение словаря с плохими хэшами: деградирует к O(n)
bad_dict = {BadHash(i): i for i in range(10000)}

# Поиск в хорошем словаре: быстро
print(timeit.timeit(lambda: GoodHash(5000) in good_dict, number=100000))

# Поиск в плохом словаре: медленно
print(timeit.timeit(lambda: BadHash(5000) in bad_dict, number=100000))

Как избежать проблем

1. Используйте встроенные типы как ключи — str, int, tuple

d = {"key1": "value1", 5: "value2", (1, 2): "value3"}  # ✅ Хорошо

1. Правильно реализуйте __hash__() и __eq__()

class Person:
    def __init__(self, id, name):
        self.id = id
        self.name = name
    
    def __hash__(self):
        return hash((self.id, self.name))  # ✅ Хороший хэш
    
    def __eq__(self, other):
        return isinstance(other, Person) and self.id == other.id and self.name == other.name

1. Помните: изменяемые объекты нельзя использовать как ключи

d = {[1, 2]: "value"}  # ❌ TypeError: unhashable type: list
d = {(1, 2): "value"}  # ✅ OK

Выводы: коллизии хэшей в Python обрабатываются автоматически и безопасно. Даже при коллизиях словарь работает корректно благодаря проверке равенства (==) после проверки хэша. Производительность может деградировать при очень плохой хэш-функции, поэтому важно правильно реализовать hash() для пользовательских типов.