logoalt Hacker News

munchler • yesterday at 8:49 PM • 1 reply • view on HN

But the hash alone shouldn't be enough to match the key. Isn't an equality check also needed to avoid a false positive? That's the idea behind a hash table, as I understand it. (I'm not a Python programmer.)

Replies

zahlman • yesterday at 8:54 PM

That equality check also considers object identity first:

  >>> class Evil:
  ...     def __init__(self, hash_value): self.hash_value = hash_value
  ...     def __eq__(self, other): return False
  ...     def __hash__(self): return self.hash_value
  ... 
  >>> e1, e2 = Evil(1), Evil(2)
  >>> {e1:1, e2:2}
  {<__main__.Evil object at ...>: 1, <__main__.Evil object at ...>: 2}
  >>> {e1:1, e2:2}[Evil(1)]
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  KeyError: <__main__.Evil object at ...>
  >>> {e1:1, e2:2}[e1]
  1
I'm pretty sure that this is meant as an optimization.

(But it does have to find the instance via the hash lookup first. This won't work if you e.g. return a random number from `__hash__`.)