Python: Почему __eq __ () не вызывается, если ключ отсутствует в словаре?

Question

В настоящее время я провожу некоторые исследования со встроенными типами Python. Я запутался, какие методы вызываются, чтобы проверить, есть ли ключ в словаре. Например, если я проверяю, есть ли ключ типа int в словаре, метод __eq__() вызывается в фоновом режиме только в том случае, если его содержит словарь dictionary.keys (). Если нет, __eq__() не вызывается.

Вот пример кода:

dict = {
  1: "Hello",
  2: "World", 
  4: "Foo"
}

assert 1 in dict.keys() # the __eq__() method of int is invoked
assert not(3 in dict.keys()) # no __eq__() method of int is invoked

Я знаю, что словарь содержит кортеж из хеша (ключа), ключа и значения. Но я немного растерялся, почему во втором утверждении не вызывается __eq__().

Чтобы проверить это поведение, я унаследовал от int и установил несколько точек останова. Вот выдержка из моего пользовательского int класса:

tint(int):
    def __new__(cls, value, *args, **kw):
        return super(tint, cls).__new__(cls, value)

    def __init__(self, value):
        super().__init__()

    def __eq__(self, other):
        return super().__eq__(other) # with breakpoints

    def __ne__(self, other):
        return super().__ne__(other) # with breakpoints

    def __hash__(self):
        return tint(super().__hash__()) # with breakpoints

Я использую Python версии 3.6.5 в Ubuntu 18.04.1 LTS.

Answer 1

Чтобы найти ключ в dict, вы сначала находите кандидатов по хешу, затем вы видите, является ли это случайностью (объекты разные, хотя хеш одинаков) или действительно ключ, который вы хотите. Так что, если вы не можете найти ничего под этим хешем, нечего эквалайзировать.

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

РЕДАКТИРОВАТЬ: CPython сохраняет дикты в массиве, где позиция первичного массива определяется хешем; если эта позиция занята, она переходит к следующей позиции кандидата математически детерминированным способом. Поскольку заполненное местоположение может, следовательно, содержать либо «правильный» хеш, либо несвязанный хеш, при поиске хеша CPython начнёт с основного места, затем продолжайте сравнивать хэши, пока не решите, что искомый ключ не найден. На данный момент хэши представляют собой простые низкоуровневые целые числа, а не объекты Python, что объясняет, почему сравнения хешей не вызывают __eq__.

Обратите внимание на симпатичную оптимизацию в источнике: для каждого кандидата CPython сначала проверяет идентичность объекта; только тогда он проверяет, все ли одинаковые хэши, и, если это так, переходит к медленной проверке, чтобы увидеть, равны ли объекты (используя PyObject_RichCompareBool, что в итоге вызывает __eq__). Почему это важно? Смотрите здесь:

class Foo:
    def __eq__(self, other):
        return False             # This shouldn't match...
    def __hash__(self):
        return 7

f = Foo()
d = { f: "Yes!" }
print(d[f])                      # ...and yet it does! :)
# => "Yes!"