Python字典如何具有相同散列的多个键？
我想了解引擎盖下的Python哈希函数。 我创build了一个自定义类，其中所有实例都返回相同的散列值。
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哈希工作原理的详细说明，请参阅我为什么早期返回速度比其他速度慢？
基本上它使用哈希来select表中的一个插槽。 如果插槽中的值和散列匹配，则比较这些项目以查看它们是否相等。
如果散列不匹配或项目不相等，则会尝试另一个插槽。 有一个公式可以select这个（我在引用的答案中描述），并逐渐引入散列值的未使用部分; 但是一旦将它们全部用完，它最终将通过哈希表中的所有槽。 这最终保证我们find一个匹配的项目或一个空的插槽。 当searchfind一个空插槽时，它会插入值或放弃（取决于我们是否添加或获取值）。
重要的是要注意的是，没有列表或桶：只有一个具有特定数量的槽的散列表，并且每个散列用于生成候选槽的序列。
这里是关于我可以放在一起的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）将槽的条目与要插入的当前条目的键的键 （通过比较我的意思是比较而不是比较）进行比较（ dictobject .c：337,344-345 ）。 如果两者匹配，则认为该条目已经存在，放弃并移动到下一个要插入的条目。 如果散列或密钥不匹配，则开始探测 。
- 探测只是意味着它通过插槽search插槽来查找空插槽。 从技术上讲，我们可以一个接一个，i + 1，i + 2，…并使用第一个可用的（即线性探测）。 但是，由于在评论中精美的解释（见dictobject.c：33-126 ），CPython使用随机探测 。 在随机探测中，下一个时隙是以伪随机顺序选取的。 该条目被添加到第一个空插槽。 对于这个讨论，用于select下一个时隙的实际algorithm并不重要（有关探测algorithm，请参见dictobject.c：33-126 ）。 重要的是插槽被探测，直到find第一个空插槽。
- 同样的事情发生的查找，只是从最初的槽我（我在哪里取决于密钥的散列）开始。 如果散列和密钥都与时隙中的条目不匹配，则开始探测，直到find一个匹配的时隙。 如果所有插槽都耗尽，则报告失败。
- 顺便说一句，如果字数是三分之二，字典将会被调整。 这可以避免查找速度变慢。 （见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我为混淆道歉。
它在散列上存储元素列表（或存储桶），然后遍历该列表，直到find该列表中的实际键。 一张图片说了超过一千个字：
在这里，你看到John Smith和Sandra Dee都散列到152 。 桶152包含它们两者。 当查找Sandra Dee它首先在桶152find该列表，然后遍历该列表，直到findSandra Dee并返回521-6955 。
以下是错误的只是在这里的上下文：在Python的维基上，你可以find（伪？）代码Python如何执行查找。
实际上有几个可能的解决办法来解决这个问题，查看维基百科的文章以获得一个很好的概述： http : //en.wikipedia.org/wiki/Hash_table#Collision_resolution
散列表，通常必须允许散列冲突！ 你会变得不幸，两件事情最终会哈希到同一个事情。 在下面，项目列表中有一组对象具有相同的散列键。 通常情况下，列表中只有一个东西，但在这种情况下，它会一直堆叠在一起。 知道它们不同的唯一方法是通过等号运算符。
发生这种情况时，性能会随着时间的推移而降低，这就是为什么您希望散列函数尽可能“随机”的原因。
在线程中，我没有看到Python将用户定义类的实例作为关键字放到字典中时究竟做了什么。 让我们读一些文档：它声明只有可哈希对象可以用作键。 Hashable是所有不可变的内置类和所有用户定义的类。
用户定义的类默认具有__cmp __（）和__hash __（）方法; 与他们，所有的对象比较不平等（除了自己）和x .__哈希__（）返回从id（x）派生的结果。
所以，如果你的类中有一个不断的__hash__，但是没有提供任何__cmp__或__eq__方法，那么你的所有实例对字典都是不相等的。 另一方面，如果您提供任何__cmp__或__eq__方法，但不提供__hash__，则您的实例在字典方面仍然不均衡。
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)
产量
{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2} {<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3} {<__main__.C object at 0x7f9672f04a10>: 3}
