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

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

242805 次浏览
小开
最佳答案

是的，它是一个哈希映射或哈希表。你可以阅读python的dict实现的描述，由Tim Peters编写，在这里。

这就是为什么你不能使用“不可哈希”的东西作为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中实现的和为什么要这样实现呢。

小开

是的。在内部，它被实现为基于Z/2 (源)上的原始多项式的开放哈希。

小开

扩展一下诺斯克洛的解释:

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

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——我估计我的桌面需要一千年才能找到一个。我稍后再回答你。)


提交答案