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

Question

我注意到当我使用用户定义的对象（覆盖 __hash__ 方法）作为我在 Python 中的字典的键时，查找时间至少增加了 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]}

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

%timeit d1['foo']

结果约为 100 ns。而

%timeit d1[mya]

结果约为 600 ns。

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

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

Answer 1

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

示例中的 "very basic" __hash__ 并不像看起来那么简单：

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

这必须读取 self 的属性 a，我会说在这种情况下会调用 object.__getattribute__(self, 'a')，并且会查找 [=48] 的值=] 在 __dict__ 中。这已经涉及计算 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 扩展来加快属性访问速度49=].

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

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

时，上面的 class 变得稍微变慢

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

Why is dictionary lookup in Python always slower when using user defined objects as keys?

python

lookup

hash

performance

dictionary