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哈希工作方式的详细说明，请参阅我对Why is early return slower than else?的回答

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

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

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

Answer 2

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

• Python字典作为哈希表实现。
• 散列表必须允许散列冲突，即使两个键具有相同的散列值，表的实现必须具有明确插入和检索键和值对的策略。
• Python dict使用开放式寻址来解决哈希冲突（如下所述）（请参阅dictobject.c:296-297）。
• Python哈希表只是一个连续的内存块（有点像数组，所以你可以通过索引进行qazxsw doi查找）。
• 表中的每个插槽可以存储一个且仅存储一个条目。这个很重要
• 表中的每个条目实际上是三个值的组合 - 。这是作为C结构实现的（参见O(1)）
• 下图是python哈希表的逻辑表示。在下图中，左边的0,1，...，i，...是哈希表中的槽的索引（它们仅用于说明目的，并且不会与表一起存储！）。 dictobject.h:51-56
• 初始化新的dict时，它以8个插槽开始。 （见

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

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

你去！ dict的Python实现检查两个键的哈希相等以及插入项时键的正常相等（dictobject.h:64-65）。总而言之，如果有两个键，==和a和b，但是hash(a)==hash(b)，那么两者都可以在Python词典中和谐地存在。但如果a!=b和hash(a)==hash(b)，那么他们不能同时在同一个字典中。

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

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

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

Answer 3

编辑：下面的答案是处理哈希冲突的可能方法之一，但不是Python如何做到这一点。下面引用的Python的wiki也是不正确的。 @Duncan给出的最佳来源是实现本身：comments我为混淆道歉。

---

它在散列中存储元素的列表（或桶），然后遍历该列表，直到它找到该列表中的实际键。一张图片说了千言万语：

在这里你看到http://svn.python.org/projects/python/trunk/Objects/dictobject.c和John Smith都哈希到Sandra Dee。水桶152包含它们。当查找152时，它首先在桶Sandra Dee中找到列表，然后循环遍历该列表，直到找到152并返回Sandra Dee。

以下是错误的，它仅适用于上下文：在521-6955上，您可以找到（伪？）代码，Python如何执行查找。

这个问题实际上有几个可能的解决方案，请查看维基百科文章以获得一个很好的概述：Python's wiki

Answer 4

哈希表，一般都要允许哈希冲突！你会发现不幸的事情，最终会有两件事情发生在同一件事上。在下面，在具有相同散列键的项列表中有一组对象。通常，该列表中只有一件事，但在这种情况下，它会将它们堆叠在同一个列表中。它知道它们不同的唯一方法是通过equals运算符。

发生这种情况时，您的性能会随着时间的推移而降低，这就是您希望散列函数尽可能“随机”的原因。

Answer 5

在线程中，当我们将字典作为键放入字典时，我没有看到python对用户定义的类的实例做了什么。让我们阅读一些文档：它声明只有可哈希的对象可以用作键。 Hashable是所有不可变的内置类和所有用户定义的类。

用户定义的类默认具有__cmp __（）和__hash __（）方法;使用它们，所有对象都比较不相等（除了它们自己）和x .__ hash __（）返回从id（x）派生的结果。

因此，如果你的班级中经常有__hash__，但没有提供任何__cmp__或__eq__方法，那么你的所有实例对于字典都是不相等的。另一方面，如果您提供任何__cmp__或__eq__方法，但不提供__hash__，则您的实例在字典方面仍然不相等。

http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

产量

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


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)