Как проверить, что найденный элемент по хэшу соответствует искомому ключу

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

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

Как отвечать

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

• идентичность: stored_key is key, самая дешёвая проверка, срабатывает, когда ищут тем же объектом;
• сохранённый хэш: если хэши не совпали, ключи точно разные, и дорогой __eq__ не вызывается. Это заметно на длинных строках и сложных объектах;
• равенство: stored_key == key. Только после него элемент считается найденным.

Если ключ не совпал, это коллизия, и поиск продолжается. При цепочках (отдельный список на ячейку) перебирается список. При открытой адресации, которую использует dict в CPython, перебираются следующие ячейки по последовательности проб, пока не встретится искомый ключ или пустая ячейка. Удалённые элементы там помечаются служебной меткой, а не очищаются, иначе поиск обрывался бы раньше времени. Таблица расширяется, когда заполнена примерно на две трети.

Отсюда контракт для своих классов: если a == b, то hash(a) == hash(b). Переопределили __eq__ без __hash__, и объект становится нехэшируемым. Поля, участвующие в хэше, должны быть неизменяемыми, удобно через @dataclass(frozen=True).

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

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

В самописной таблице при вставке просто кладут пару в ячейку по индексу. Тогда второй ключ с тем же индексом молча затирает первый, хотя вставка обязана сначала сравнить ключ и при несовпадении искать дальше.

Меняют объект, который уже лежит ключом. Хэш меняется, элемент остаётся в старой ячейке и перестаёт находиться, хотя формально он в словаре есть. Отдельный курьёз: float('nan') не равен сам себе, поэтому находится только тем же самым объектом.