[New-bugs-announce] [issue38105] hash collision when hash(x) == -2 causes many calls to __eq__

[Guido Imperiale]

New submission from Guido Imperiale <crusaderky at gmail.com>:

Take two objects where hash(a) == hash(b) == -2 exactly, but a != b,
When they are inserted in a dict or set, the __eq__ method is invoked a whopping 13 times.

Does this have something to do with the special case of hash(-1) = -2?

class C:
    def __init__(self, x, h):
        self.x = x
        self.h = h

    def __eq__(self, other):
        print(f"{self}.__eq__({other})")
        return self.x == other.x

    def __hash__(self):
        print(f"{self}.__hash__")
        return self.h

    def __repr__(self):
        return f"C({self.x, self.h})"

>>> {C(1, -2), C(2, -2)}
C((1, -2)).__hash__
C((2, -2)).__hash__
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
C((1, -2)).__eq__(C((2, -2)))
{C((1, -2)), C((2, -2))}

>>> {C(1, -3), C(1, -3)}
C((1, -3)).__hash__
C((1, -3)).__hash__
C((1, -3)).__eq__(C((1, -3)))
{C((1, -3))}

>>> {C(1, -1), C(1, -1)}
C((1, -1)).__hash__
C((1, -1)).__hash__
C((1, -1)).__eq__(C((1, -1)))

>>> {C(1, -2), C(1, -2)}
C((1, -2)).__hash__
C((1, -2)).__hash__
C((1, -2)).__eq__(C((1, -2)))
{C((1, -2))}

----------
messages: 351798
nosy: crusaderky
priority: normal
severity: normal
status: open
title: hash collision when hash(x) == -2 causes many calls to __eq__
type: performance
versions: Python 3.7, Python 3.8

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue38105>
_______________________________________