为什么Python字典可以具有相同散列的多个键?
问题内容:
我想了解幕后的Pythonhash
函数。我创建了一个自定义类,其中所有实例都返回相同的哈希值。
class C:
def __hash__(self):
return 42
我只是假设上述类的一个实例随时都可以位于中dict
,但是实际上adict
可以具有相同散列的多个元素。
c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements
我进行了更多的实验,发现如果我重写该__eq__
方法以使该类的所有实例都相等,则dict
仅允许一个实例。
class D:
def __hash__(self):
return 42
def __eq__(self, other):
return True
p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element
因此,我很想知道adict
可以如何将多个元素具有相同的哈希值。
问题答案:
有关Python哈希的工作原理的详细说明,请参见我的答案,为什么早期返回比其他方法慢?
基本上,它使用哈希在表中选择一个插槽。如果插槽中有一个值并且哈希值匹配,它将比较各项以查看它们是否相等。
如果哈希值不匹配或项目不相等,则尝试另一个槽。有一个公式可以选择(我在参考答案中对此进行了描述),并且它会逐渐提取哈希值的未使用部分;但一旦将其全部用尽,它将最终在哈希表中的所有插槽中工作。这样可以保证最终我们找到匹配的项目或空的插槽。当搜索找到一个空插槽时,它会插入值或放弃(取决于我们要添加还是获取值)。
需要注意的重要一点是,没有列表或存储桶:只有具有特定数量的插槽的哈希表,并且每个哈希都用于生成一系列候选插槽。