python - 为什么在使用用户定义的对象作为键时，Python 中的字典查找总是比较慢？

Question

我注意到，当我在 Python 中使用用户定义的对象(覆盖 __hash__ 方法)作为我的字典的键时，查找时间至少增加了 5 倍。

即使我使用非常基本的散列方法(例如以下示例)，也会观察到此行为:

class A:
    def __init__(self, a):
        self.a = a
    def __hash__(self):
        return hash(self.a)
    def __eq__(self, other):
        if not isinstance(other, A):
            return NotImplemented
        return (self.a == other.a and self.__class__ == 
                other.__class__)

# get an instance of class A
mya = A(42)
# define dict
d1={mya:[1,2], 'foo':[3,4]}

如果我通过两个不同的 key 对访问进行计时，我会观察到性能上的显着差异

%timeit d1['foo']

结果在 ~ 100 ns 内。鉴于

%timeit d1[mya]

结果约为 600 ns。

如果我删除了 __hash__ 和 __eq__ 方法的覆盖，性能与默认对象处于同一水平

有没有办法避免这种性能损失并仍然实现自定义哈希计算？

Answer 1

自定义类的默认 CPython __hash__ 实现是用 C 语言编写的，并使用对象的内存地址。因此，它不必从对象中访问绝对值并且可以非常快速地完成，因为它只是 CPU 中的单个整数运算，即使那样也是如此。

示例中的“非常基本的”__hash__ 并不像看起来那么简单:

def __hash__(self):
    return hash(self.a)

这必须读取 self 的属性 a，我会说在这种情况下将调用 object.__getattribute__(self, 'a') ，这将在 __dict__ 中查找 'a' 的值。这已经涉及计算 hash('a') 并查找它。然后，返回值将传递给hash。

---

回答附加问题:

Is there a way to implement a faster __hash__ method that returns predictable values, I mean that are not randomly computed at each run as in the case of the memory address of the object ?

任何访问对象属性的操作都会比不需要访问属性的实现慢，但是您可以通过使用 __slots__ 来加快属性访问速度，或为该类实现高度优化的 C 扩展。

然而，还有另一个问题:这真的是个问题吗？我真的不敢相信应用程序会因为慢的 __hash__ 而变慢。 __hash__ 应该仍然非常快，除非字典有数万亿个条目，但那样的话，其他所有内容都会变慢并要求进行更大的更改...

---

我做了一些测试，必须进行更正。在这种情况下，使用 __slots__ 根本无济于事。我的测试实际上表明，在 CPython 3.7 中，当使用 __slots__ 时，上述类变得稍微慢。