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

Question

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

Answer 1

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

这就是为什么你不能使用'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）发生冲突。）

是。在内部，它基于Z / 2上的原始多项式实现为开放散列（源）。

扩展nosklo的解释：

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

Answer 3

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 4

是。在内部，它基于Z / 2上的原始多项式实现为开放散列（源）。

Answer 5

扩展nosklo的解释：

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