Что происходит при коллизии ключей в dictionary

При коллизии ключей в Python словаре используется метод открытой адресации с двойным хешированием. Python сохраняет все ключи, значения и хеши в массиве, и если два ключа имеют одинаковый хеш, интерпретатор ищет следующую свободную ячейку в этом массиве.

Пример:

d = {}
d['key1'] = 'value1'  # допустим хеш(key1) = 123
d['key2'] = 'value2'  # допустим хеш(key2) = 123 (коллизия)
# Python найдет следующую свободную ячейку после 123

Важные моменты:

1. Порядок вставки влияет на положение элементов при коллизиях
2. Поиск значения сначала проверяет хеш, затем сравнивает ключи через eq
3. При большом количестве коллизий производительность снижается до O(n)

Для пользовательских объектов важно правильно реализовать hash и eq.