Python字典是哈希表的一个例子吗？

Question

Python中基本的数据结构之一是字典，它允许记录“键”以查找任何类型的“值”。 它是内部实现为哈希表吗？ 如果不是，那是什么？

- Tommy Herbert

---

如果您对技术细节感兴趣，可以阅读《编写优美代码》（Beautiful Code）一书中与Python的dict实现有关的文章。我会将其翻译为：假如你想了解技术细节，可以在Beautiful Code这本书中找到一篇介绍Python dict实现内部机制的文章。 - Torsten Marek

那是《编写优美代码》中我最喜欢的章节之一。 - DGentry

这是Brandon Craig Rhodes讲解Python字典如何工作的演讲视频，链接为https://www.youtube.com/watch?v=C4Kc8xzcA68。 - chandola

我一直在寻找一个代表字典在内存和CPython中实现的图表。感谢您提供了这本书的参考！ - Chen A.

Answer 1

是的，它是哈希映射或哈希表。您可以阅读Tim Peters撰写的有关Python字典实现的描述，在此处查看。

这就是为什么您不能使用像列表这样的“不可哈希”对象作为字典键的原因：

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

你可以阅读更多关于哈希表的内容或者查看它在Python中是如何被实现的以及为什么要这样实现。

- nosklo

---

Tim Peters的链接似乎已经失效了，有没有其他可用的干净链接？ - Matt Alcock

@MattAlcock：我已经更新了链接。有时（通常是由于某人想要在某个地方删除他们的电子邮件地址），Python列表档案会重新构建，电子邮件的ID会改变，从而破坏这些链接。现在，pydotorg管理员通常会尽量避免这种情况发生。 - Martijn Pieters

但是使用.keys()可以检索键列表。真正的哈希表不会存储键，只会存储哈希值以节省空间。 - noɥʇʎԀʎzɐɹƆ

Python字典实现的更完整描述在此处： http://www.laurentluce.com/posts/python-dictionary-implementation/ - Daniel Goldfarb

@noɥʇʎԀʎzɐɹƆ - 只有密钥的引用和哈希值被存储，而密钥本身并没有被存储。 - nosklo

Answer 2

Python 字典不仅仅是通过 hash() 进行表查找。通过粗略的实验，我发现了这个哈希碰撞：

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

然而它并不会破坏字典：

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

检查：

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

可能在哈希（hash()）之外还有另一种查找级别，可以避免字典键之间的冲突。或者也许dict()使用了不同的哈希函数。

（顺便说一下，这是在Python 2.7.10中的情况。在Python 3.4.3和3.5.0中的情况相同，在hash(1.1) == hash(214748749.8)处发生冲突。）

（我没有在Python 3.9.6中发现任何冲突。由于哈希值更大-- hash(1.1) == 230584300921369601 -- 所以我估计我的桌面需要一千年才能找到一个冲突。所以我会在此后再给你答复。）

- Bob Stein

---

碰撞是不可避免的。集合S可能包含无限多个项，而你希望它能够散列成计算机可以存储的数字。每个可用的哈希表实现都解决了碰撞问题，最常见的两种方法是a) 开放寻址和b) 链接法。仅因为它没有使用完美哈希，就不意味着它不是哈希表。 - TurnipEntropy

一般情况下会发生碰撞，因为有无限可能的可哈希值和有限的哈希码。即使是哈希表也必须以某种方式处理碰撞。 - Yanfeng Liu

我相信这些恰好是TurnipEntropy所提出的相同观点。 - Bob Stein

在Python 3.7中，实际上有2E20减1个可能的哈希值。从-1E20减1到（+）1E20减1。尝试hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')这会给出一个19位十进制数 - 如果你够极客，那就是-4037225020714749784。继续用自己的话说吧，孩子们，哈希仍然是一个19位数。我假设在Python中可以哈希的字符串长度有限，但可以肯定的是，可以哈希的字符串比可能的值要多得多。顺便说一下，hash(False)=0。 - Will Croxford

它之所以不会破坏字典，是因为在底层，重复的值是使用链表实现的，并且存储在指向它们生成的键的指针旁边。 - TrancendentalObject

有很多。hash(0) = 0; hash(2 ** 61 - 1) = 0; hash(-2 ** 61 + 1) = 0; - Nitish Agarwal

Answer 3

是的。在内部，它是基于Z/2上的原始多项式实现的开放哈希（来源）。

- Ben Hoffstein

Answer 4

在nosklo的解释基础上，进一步解释：

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']

- Jeremy Cantrell