Как происходит разрешение коллизий в словаре Python

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

Основные моменты:

1. Используется квадратичный probing (не линейный) для поиска свободного слота
2. Размер таблицы всегда степень двойки
3. При заполнении на 2/3 таблица расширяется

Пример коллизии:

class BadHash:
    def __hash__(self):
        return 1  # Все объекты будут иметь одинаковый хэш

a = BadHash()
b = BadHash()
d = {a: 'first', b: 'second'}  # Оба объекта попадут в словарь
print(d[a], d[b])  # Выведет 'first' 'second'

При поиске ключа сначала проверяется его хэш, затем сравнивается сам ключ через eq. Если не совпадает - продолжается поиск по probing-последовательности.