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

Question

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

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

Answer 2

除了在hash（）上进行表查找之外，Python词典还必须有更多内容。通过残酷的实验，我发现了这种哈希冲突：

>>> 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)。）

Answer 3

为了扩展nosklo的解释：

a = {}

b = ['some', 'list']

a[b] = 'some' # this won't work

a[tuple(b)] = 'some' # this will, same as a['some', 'list']