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

问题描述：

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

解决方案 1：

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

这就是为什么你不能使用“不可哈希”的东西作为字典键，比如列表：

>>> 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 中是如何实现的以及为什么以这种方式实现。

解决方案 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——我估计我的桌面需要一千年才能找到一个。所以我会就此事回复你。）

解决方案 3：

是的。它的内部实现是基于 Z/2 上的本原多项式的开放哈希算法 (来源)。

解决方案 4：

扩展 nosklo 的解释：

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