为什么Python字典可以有多个具有相同散列的键？
我正在尝试理解Pythonhash
在引擎盖下运行。我创建了一个自定义类，其中所有实例都返回相同的散列值。
class C:
def __hash__(self):
return 42我只是假设上面的类只有一个实例可以在dict在任何时候，但实际上dict可以有多个具有相同散列的元素。
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所以我很好奇地想知道dict可以有多个具有相同散列的元素。
回答 5
Stack Overflow用户
发布于 2012-01-26 05:26:54
有关Python散列工作原理的详细描述，请参阅我对
为什么早期返回的速度比其他时间要慢？基本上，它使用散列来挑选表中的一个位置。如果槽中有一个值并且哈希匹配，它会比较这两个项目，看它们是否相等。如果散列匹配但项不相等，则它会尝试另一个槽。有一个公式来挑选它(我在参考答案中描述过)，它逐渐拉入哈希值中未使用的部分；但一旦用完它们，它最终将在哈希表中的所有槽中以自己的方式工作。这保证了我们最终要么找到匹配的项目，要么找到一个空的位置。当搜索找到一个空槽时，它会插入该值或放弃(这取决于我们是在添加还是获取一个值)。
需要注意的重要一点是，没有列表或存储桶:只有一个哈希表，其中包含特定数量的槽，每个哈希用于生成候选槽序列。
Stack Overflow用户
发布于 2012-01-27 01:40:18
以下是我能够汇总的有关Python的所有内容(可能比任何人都想知道的要多；但答案是全面的)。对…的呼喊
邓肯因为我指出Python dicts使用老虎机，并把我带到了这个兔子洞。Python字典实现为哈希表。
哈希表必须允许散列冲突即，即使两个键具有相同的散列值，表的实现也必须具有明确地插入和检索键和值对的策略。Python dict使用开放寻址要解决散列冲突(如下所述)(请参阅Dictoject.c:296-297)。
Python哈希表只是一个有争议的内存块(有点像数组，所以您可以O(1)按索引查找)。表中的每个槽可以存储且只能存储一个条目。这一点很重要每个条目表中实际上是三个值的组合-。这是作为C结构实现的(请参见Dictoject.h:51-56)
下图是python哈希表的逻辑表示。在下图中，0，1，...，i，...左边是插槽在哈希表中(它们只是为了说明的目的，显然没有与表一起存储！)。Python哈希表的逻辑模型-+-+ 0| |-+-+ 1| ... |-+-+ .| ... |-+ i| ...|-+-+ .| ... |-+-+ n| ... |-+
当一个新的字典被初始化时，它从8开始插槽。(请参阅dictobject.h:49)
当向表中添加条目时，我们从一些槽开始，这是i基于键的散列的。CPython使用初始。i = hash(key) & mask在哪里mask = PyDictMINSIZE - 1，但这并不重要)。只需注意，检查的初始插槽i取决于哈希钥匙。如果该插槽为空，则将该条目添加到该插槽中(通过条目，我的意思是)。但是如果这个位置被占用了怎么办？很可能是因为另一个条目具有相同的散列(散列冲突！)
如果插槽被占用，CPython (甚至是PyPy)会比较散列和密钥)我的意思是==比较比较而is不是槽中的条目与要插入的当前条目的键的比较)(dictobject.c:337344-345)。如果两者都有匹配，则它认为该条目已经存在，放弃并移动到下一个要插入的条目。如果散列或键不匹配，则启动探测。
探测只是意味着它逐个搜索插槽以找到一个空插槽。从技术上讲，我们可以一个接一个地去，i+1，i+2，..。并使用第一个可用的方法(即线性探测)。但原因在评论中解释得很好(请参阅Dictoject.c:33-126)，CPython使用随机探测。在随机探测中，以伪随机顺序挑选下一个时隙。该条目被添加到第一个空槽中。对于这个讨论，用于挑选下一个槽的实际算法并不真正重要(请参见Dictoject.c:33-126用于探测的算法)。重要的是探测插槽，直到找到第一个空插槽。
同样的事情也发生在查找上，只是从初始的槽i开始(其中i依赖于键的散列)。如果散列和键都不匹配槽中的条目，它将开始探测，直到找到一个匹配的槽。如果所有插槽都已耗尽，则报告失败。
顺便说一句，如果字典是三分之二满的，它将被调整大小。这可以避免降低查找速度。(请参Dictoject.h:64-65)这就对了！Python实现的dict检查两个键的散列相等和正常相等(==)。所以总而言之，如果有两个密钥，a和b和hash(a)==hash(b，但是a!=b，然后两者可以在Python字典中和谐共存。但是如果hash(a)==hash(b)和a==b，那么它们不可能都在同一个字典中。
因为我们必须在每次哈希冲突之后进行探测，太多哈希冲突的一个副作用是查找和插入将变得非常慢(正如Duncan在评论)。
我想对我的问题的简短回答是，“因为它是如何在源代码中实现的;)”
虽然知道这一点很好(对于极客的观点？)，但我不确定它如何在现实生活中使用。因为除非您试图显式地破坏某些东西，否则为什么两个不相等的对象会有相同的散列呢？
Stack Overflow用户
发布于 2012-01-26 05:04:14
编辑：下面的答案是处理散列冲突的可能方法之一，但它是注释Python是如何做到这一点的。下面提到的Python的wiki也是不正确的。下面@Duncan给出的最好的源代码是实现本身：
https://github.com/python/cpython/blob/master/Objects/dictobject.c
我为我的混淆道歉。
它在散列中存储一个元素列表(或存储桶)，然后遍历该列表，直到在该列表中找到实际的键。一张图片比千言万语更能说明问题：
在这里你可以看到John Smith和Sandra Dee两者都散列到152.。存储桶152
包含这两个元素。当你抬头看Sandra Dee的时候它首先在存储桶中查找152列表，然后遍历该列表，直到Sandra Dee被找到并返回521-6955。
下面的内容是错误的，这里只针对上下文：打开Python的维基你可以找到(伪？)编写Python如何执行查找的代码。这个问题实际上有几种可能的解决方案，请查看wikipedia文章以获得一个很好的概述：http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
https://stackoverflow.com/questions/9010222
复制相似问题