是一个Python字典的哈希表的例子吗？(Is a Python dictionary an exa

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

Answer 1:

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

这就是为什么你不能使用的东西“不哈希的”作为字典键，就像一个列表：

>>> 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(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

也许还有另一种查找水平超出哈希（），避免字典的键之间的碰撞。 或者，也许字典（）使用不同的哈希值。

（顺便说一句，这在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']

文章来源: Is a Python dictionary an example of a hash table?