Python dict如何具有相同哈希的多个键？

Question

我试图了解引擎盖下的python哈希函数.我创建了一个自定义类,其中所有实例都返回相同的哈希值.

class C(object):
    def __hash__(self):
        return 42

我只是假设上面的类中只有一个实例可以随时出现在一个集合中,但实际上一个集合可以有多个具有相同散列的元素.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print x
# {<__main__.C object at 0x83e98cc>:'c', <__main__.C object at 0x83e98ec>:'d'}
# note that the dict has 2 elements

我进行了一些实验,发现如果我重写__eq__方法使得类的所有实例比较相等,那么该集只允许一个实例.

class D(C):
    def __eq__(self, other):
        return hash(self) == hash(other)

p, q = D(), D()
y = {p:'p', q:'q'}
print y
# {<__main__.D object at 0x8817acc>]: 'q'}
# note that the dict has only 1 element

所以我很想知道dict有多个具有相同哈希的元素.谢谢!

注意:编辑问题以给出dict(而不是set)的例子,因为答案中的所有讨论都是关于dicts的.但这同样适用于集合; 集合也可以有多个具有相同散列值的元素.

Answer 1

以下是我能够整理的Python dicts的所有内容(可能比任何人都想知道的更多;但答案是全面的).向Duncan大声喊出,他指出Python决定使用插槽并引导我走下这个兔子洞.

• Python字典作为哈希表实现.
• 散列表必须允许散列冲突,即使两个键具有相同的散列值,表的实现必须具有明确插入和检索键和值对的策略.
• Python dict使用开放式寻址来解决散列冲突(如下所述)(参见dictobject.c:296-297).
• Python哈希表只是一个连续的内存块(有点像数组,所以你可以O(1)通过索引进行查找).
• 表中的每个插槽可以存储一个且仅存储一个条目.这个很重要
• 表中的每个条目实际上是三个值的组合 -.这是作为C结构实现的(参见dictobject.h:51-56)

• 下图是python哈希表的逻辑表示.在下图中,左边的0,1,...,i,...是哈希表中的槽的索引(它们仅用于说明目的,并且不会与表一起存储!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• 初始化新的dict时,它以8 个插槽开始.(见dictobject.h:49)

• 在向表中添加条目时,我们从一些插槽开始,i这是基于密钥的散列.CPython使用初始i = hash(key) & mask.哪里mask = PyDictMINSIZE - 1,但那并不重要).请注意,检查的初始插槽i取决于密钥的哈希值.
• 如果该插槽为空,则该条目将添加到插槽中(通过条目,我的意思是<hash|key|value>).但如果那个插槽被占用怎么办？很可能是因为另一个条目具有相同的哈希值(哈希冲突!)
• 如果插槽被占用,CPython(甚至PyPy)将插槽中的条目与要插入的当前条目的键的散列和键(通过比较,我的意思是==比较而不是is比较)进行比较(dictobject.c: 337,344-345).如果两者都匹配,则认为该条目已存在,放弃并继续下一个要插入的条目.如果散列或密钥不匹配,则开始探测.
• 探测只是意味着它按插槽搜索一个空槽.从技术上讲,我们可以逐个进行,i + 1,i + 2,...并使用第一个可用的(线性探测).但是由于在评论中精美解释的原因(参见dictobject.c:33-126),CPython使用随机探测.在随机探测中,以伪随机顺序拾取下一个时隙.该条目将添加到第一个空槽中.对于这个讨论,用于选择下一个槽的实际算法并不重要(参见dictobject.c:33-126,用于探测算法).重要的是探测插槽直到找到第一个空插槽.
• 同样的事情发生在查找中,只是从初始插槽i开始(其中i取决于密钥的散列).如果散列和密钥都与插槽中的条目不匹配,则它开始探测,直到找到具有匹配的插槽.如果所有插槽都耗尽,则报告失败.
• 顺便说一句,如果三分之二已满,则会调整大小.这可以避免减慢查找速度.(见dictobject.h:64-65)

你去!dict的Python实现检查两个键的哈希相等和==插入项时键的正常相等().因此,在总结,如果有两个按键,a和b和hash(a)==hash(b),但是a!=b,那么两者都可以在和谐Python字典存在.但如果hash(a)==hash(b) 和 a==b,那么他们不可能都在同一个词中.

因为我们必须在每次哈希冲突之后进行探测,所以太多哈希冲突的一个副作用是查找和插入将变得非常慢(正如Duncan在评论中指出的那样).

我想我的问题的简短答案是,"因为它是如何在源代码中实现的;"

虽然这很有用(对于极客点？),但我不确定它如何在现实生活中使用.因为除非你试图明确地破坏某些东西,为什么两个不相等的对象具有相同的散列？

Answer 2

有关Python的哈希工作方式的详细说明,请参阅我的答案为什么提前返回比其他更慢？

基本上它使用哈希来选择表中的一个槽.如果插槽中有值且散列匹配,则会比较这些项以查看它们是否相等.

如果哈希不匹配或项目不相等,则它尝试另一个槽.有一个公式来选择这个(我在引用的答案中描述),它逐渐拉入哈希值的未使用部分; 但是一旦它全部使用它们,它最终将通过哈希表中的所有插槽.这保证了我们最终找到匹配的项目或空槽.当搜索找到一个空槽时,它会插入值或放弃(取决于我们是添加还是获取值).

需要注意的重要事项是没有列表或桶:只有一个具有特定数量的槽的哈希表,每个哈希用于生成一系列候选槽.

Answer 3

编辑:下面的答案是处理哈希冲突的可能方法之一,但不是 Python如何做到这一点.下面引用的Python的wiki也是不正确的.@Duncan给出的最佳来源是实现本身:http://svn.python.org/projects/python/trunk/Objects/dictobject.c 我为混淆道歉.

它在散列中存储元素的列表(或桶),然后遍历该列表,直到它找到该列表中的实际键.一张图片说了千言万语:

在这里你看到John Smith并且Sandra Dee都哈希到152.铲斗152包含它们.查找时Sandra Dee首先找到存储桶中的列表152,然后遍历该列表直到Sandra Dee找到并返回521-6955.

以下是错误的,它仅适用于上下文:在Python的wiki上,您可以找到(伪？)代码,Python如何执行查找.

实际上有几个可能解决这个问题的方法,请查看维基百科文章以获得一个很好的概述:http://en.wikipedia.org/wiki/Hash_table#Collision_resolution