Python字典是哈希表的一个例子吗?
-
02-07-2019 - |
题
Python中的一个基本数据结构是字典,它允许用户记录“密钥”。用于查找“值”任何类型。这在内部实现为哈希表吗?如果没有,那是什么?
解决方案
是的,它是一个哈希映射或哈希表。您可以阅读由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字典必须比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']
不隶属于 StackOverflow