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

Question

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

Answer 1

是的,它是一个哈希映射或哈希表.您可以阅读python的字典实现的描述,由Tim彼得斯书面,这里.

这就是为什么你不能使用'nothable'作为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

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).)

Answer 3

是.在内部,它实现为基于Z/2上的本原多项式的开放散列(源).

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']