in в dict Python и any: как равенство и хэш ключей влияют на поиск

Почему проверка принадлежности в словаре Python через in не равна any: роль __eq__ и __hash__, как несогласованный хэш ломает поиск и создаёт дубликаты ключей.

Когда вы используете оператор in в Python для проверки принадлежности, документация предлагает простую ментальную модель: для контейнерных типов, x in y ведёт себя как any(x is e or x == e for e in y). Эта схема замечательно работает для последовательностей, но может дать сбой для отображений вроде dict, если ваши ключи не по-настоящему хэшируемы. Ниже — минимальный воспроизводимый разбор, показывающий, почему проверка принадлежности в словаре может отличаться от наивного any(...) по тем же ключам.

Проблема, воспроизведение

class Box:
    def __init__(self, payload):
        self.payload = payload
    def __eq__(self, other):
        return self.payload == other.payload
    __hash__ = object.__hash__

x = Box(1)
y = Box(2)
z = Box(3)

seq_boxes = [x, y, z]

print("Box(2) in seq_boxes:")
print("   ", Box(2) in seq_boxes)

Box(2) in seq_boxes:
    True

Тот же объект, используемый как ключ в отображении, внезапно ведёт себя иначе.

box_map = {x: "ekam", y: "dve", z: "trini"}

print("box_map[Box(2)]:")
try:
    print(box_map[Box(2)])
except KeyError:
    print("    KeyError")

print()
print("Box(2) in box_map:")
print("   ", Box(2) in box_map)

box_map[Box(2)]:
    KeyError

Box(2) in box_map:
    False

Если в документации сказано, что это эквивалентно any(x is e or x == e for e in y), почему прямой тест, кажется, противоречит тому, что сообщает dict?

def contains_probe(item, container):
    return any(item is cand or item == cand for cand in container)

print("contains_probe(Box(2), box_map):")
print("   ", contains_probe(Box(2), box_map))

contains_probe(Box(2), box_map):
    True

Итерация по ключам отображения показывает, что проверка равенства действительно срабатывает:

def probe_trace(item, container):
    for cand in container:
        print(item is cand, item == cand)

print("probe_trace(Box(2), box_map):")
probe_trace(Box(2), box_map)

probe_trace(Box(2), box_map):
False False
False True
False False

Что на самом деле происходит

Проблема не в операторе in. Дело в том, что dict — это отображение, а отображения работают с хэшируемыми ключами. Определение однозначно: «Хэшируемые объекты, которые считаются равными, должны иметь одинаковое значение хэша». Если вы определяете равенство в своём классе, но оставляете __hash__ указывать на object.__hash__, вы получаете хэш по идентичности, пока равенство сравнивает содержимое. Два разных экземпляра Box(2) будут равны, но их хэши не совпадают. Это нарушает инварианты, от которых dict зависит при проверке принадлежности и поиске.

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

Для контейнерных типов, таких как list, tuple, set, frozenset, dict или collections.deque, выражение x in y эквивалентно any(x is e or x == e for e in y).

Эта эквивалентность относится к смыслу «содержится/не содержится», а не к гарантии реализации, которая в словарях обходит хеширование. В dict операция проверки принадлежности использует хеш как часть обычного алгоритма. Если равные объекты не разделяют стабильный хэш, поиск проваливается, даже если наивный any(...) по ключам нашёл бы равенство.

Практические последствия в реальном коде

Последствия проявляются сразу, как только вы добавляете в словарь кажущиеся «равными» ключи. Вместо обновления существующей записи вы получаете несколько записей для одного логического ключа.

>>> m = {Box(1): "first time"}
>>> len(m)
1
>>> m[Box(1)] = "second time"
>>> len(m)
2

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

Как исправить

Сделайте хэш согласованным с равенством. Если равенство сравнивает payload, то и хэш должен вычисляться из payload.

class Box:
    def __init__(self, payload):
        self.payload = payload
    def __eq__(self, other):
        return self.payload == other.payload
    def __hash__(self):
        return hash(self.payload)

С этой правкой, пока значения payload сами по себе хэшируемы, операции dict — включая проверку принадлежности и индексацию — будут согласованы с вашей семантикой равенства. «Объект отображения сопоставляет хэшируемые значения с произвольными объектами», и предоставив корректный хэш, вы выполняете этот контракт.

Важная оговорка про изменяемость

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

>>> k = Box(1)
>>> store = {}
>>> store[k] = "one"
>>> k in store
True
>>> k.payload = 3
>>> k in store
False
>>> # Теперь индексирование и поиск будут завершаться KeyError для любого варианта

Как только состояние ключа, влияющее на хэш, изменилось, исходная запись становится фактически недоступной через обычные операции dict. Требование «значение хэша не меняется на протяжении жизни объекта» не является необязательным, если объект используется как ключ.

Почему это важно

Опора только на равенство без согласованного хэша подрывает работу отображений Python. Код, выглядящий правильным на первый взгляд, приведёт к тихим логическим ошибкам: дубликатам ключей для одинаковых значений, проваленным проверкам принадлежности и некорректным поискам. Понимание того, что принадлежность в dict держится на контракте «хэш и равенство», помогает избежать трудных для отладки проблем и сохраняет характеристику быстродействия, ради которой отображения и спроектированы.

Итоги

Если вы определяете __eq__ для класса, который будет ключом dict или элементом set, определяйте и __hash__, чтобы равные экземпляры имели один и тот же хэш. Не изменяйте поля, участвующие в вычислении хэша, пока объект используется как ключ. При соблюдении этих условий оператор in, проверка принадлежности в словаре и прямая индексация будут согласованы с вашей семантикой равенства.