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

Question

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

原文由 Tommy Herbert 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 发布，翻译遵循 CC BY-SA 3.0 许可协议

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 发布，翻译遵循 CC BY-SA 4.0 许可协议