Что происходит при коллизии хешей в словаре и как разрешается ситуация с одинаковым хешем у разных ключей

Что проверяют

Знаете ли вы, что происходит внутри dict, и понимаете ли контракт между __hash__ и __eq__. Вопрос отделяет тех, кто пользовался словарём, от тех, кто может объяснить, почему доступ по ключу считается быстрым и когда он перестаёт быть таковым.

Как отвечать

Коллизия это совпадение не хеша целиком, а номера слота: таблица меньше пространства хешей, поэтому берутся только младшие биты.

CPython разрешает коллизии открытой адресацией, а не цепочками. При занятом слоте пробуется следующий по псевдослучайной последовательности, в которой участвуют и старшие биты хеша, и так до свободного места. Неверного результата это не даёт: дойдя до занятого слота, интерпретатор сравнивает сами ключи, сначала по тождеству, потом через ==, и продолжает пробирование, если ключ не тот.

Что стоит добавить:

• контракт односторонний: равные объекты обязаны иметь равные хеши, обратное неверно;
• hash(1) == hash(1.0) == hash(True), поэтому в словаре {1: "a", True: "b"} окажется один элемент;
• хеш строк рандомизируется при старте процесса, это защита от подбора ключей в одну корзину, и порядок обхода множества строк между запусками меняется;
• доступ константный в среднем и линейный в вырожденном случае, когда все ключи ложатся в одну последовательность проб;
• таблица расширяется при заполнении примерно на две трети, и все элементы перераскладываются заново.

Где спотыкаются

Пересказывают учебник про метод цепочек со связным списком в каждой корзине. Это описание хеш-таблицы вообще, но не того, что делает CPython: списков в слотах нет, есть пробирование. Ответ про цепочки интервьюер засчитает как незнание реализации.

Второе: переопределяют __eq__ и забывают про __hash__. В Python 3 класс с собственным __eq__ и без __hash__ становится нехешируемым, и в словарь его уже не положить. Обратная беда не лучше: с хешем от родителя равные объекты получат разные хеши и потеряются в таблице.

Третье: берут в ключи изменяемое состояние. Объект кладут в словарь, потом меняют поле из хеша, и элемент перестаёт находиться по самому себе, хотя физически лежит на месте. Ключи должны быть неизменяемыми, и ровно поэтому список ключом быть не может.