Python字典如何具有相同散列的多个键？

 

我想了解引擎盖下的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的例子（而不是set），因为答案中的所有讨论都是关于dicts的。 但是这同样适用于集合; 集合也可以具有多个具有相同散列值的元素。

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

基本上它使用哈希来选择表中的一个插槽。 如果插槽中有一个值和哈希匹配，则比较这些项目以查看它们是否相等。

如果散列不匹配或者项目不相等，则它会尝试另一个插槽。 有一个公式可以选择这个（我在引用的答案中描述），它逐渐引入散列值的未使用部分; 但一旦将它们全部使用完毕，它最终将通过散列表中的所有插槽。 这最终保证我们找到一个匹配的项目或一个空的插槽。 当搜索找到空插槽时，它会插入值或放弃（取决于我们是添加还是获取值）。

重要的是要注意的是，没有列表或存储桶：只有一个具有特定数量的槽的散列表，并且每个散列用于生成候选槽的序列。

以下是我能够放在一起的所有Python字典（可能比任何人都想知道的更多;但答案是全面的）。 Duncan大声指出Python的字典使用插槽并将我引向这个兔子洞。

  • Python字典被实现为散列表 。
  • 散列表必须允许散列冲突，即使两个键具有相同的散列值，表的实现必须具有明确插入和检索键和值对的策略。
  • Python字典使用开放寻址来解决散列冲突（如下所述）（请参阅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|      ...        |
-+-----------------+

  • 当一个新的字典被初始化时，它从8个插槽开始。 （请参阅dictobject.h：49）

  • 当向表中添加条目时，我们从一些槽开始， i基于密钥散列的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）。 重要的是插槽被探测直到找到第一个空插槽。
  • 同样的事情发生的查找，只是从最初的槽我开始（我在哪里取决于密钥的散列）。 如果散列和密钥都与插槽中的条目不匹配，则会开始探测，直到找到一个匹配的插槽。 如果所有插槽都耗尽，则报告失败。
  • 顺便说一句，该字典将调整大小，如果它是三分之二满。 这可以避免查找速度变慢。 （请参阅dictobject.h：64-65）

    • 你走了！ dict的Python实现检查两个键的哈希相等和插入项目时键的正常相等（ == ）。 因此，总而言之，如果有两个键， a和b和hash(a)==hash(b) ，但是a!=b ，那么它们在Python字典中可以和谐地存在。 但是，如果hash(a)==hash(b) 和 a==b ，那么它们不能同时在同一个字典中。

    因为我们必须在每次散列冲突之后进行探测，所以散列冲突太多的副作用是查找和插入将变得非常缓慢（正如Duncan在注释中指出的那样）。

    我想我的问题的简短答案是，“因为这是如何在源代码中实现的;）”

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

    编辑 ：下面的答案是处理散列冲突的可能方法之一，但不是 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

    链接地址: http://www.djcxy.com/p/17529.html

    上一篇: How can Python dict have multiple keys with same hash?

    下一篇: Process all arguments except the first one (in a bash script)