我有一个关于Python字典实现的问题。
似乎Python会为所有键维护一个搜索顺序,例如如果您执行以下操作:
a = {}
a[3] = 1
a[0] = 2
a = {0:2, 3:1}
Python会自动更改我的插入顺序。由于Python声称字典是无序的集合,我不太理解为什么Python会保持这样的搜索顺序。Python是通过哈希表实现字典并存储另一个集合来进行索引排序吗?
希望我表述清楚了。
谢谢。
我有一个关于Python字典实现的问题。
似乎Python会为所有键维护一个搜索顺序,例如如果您执行以下操作:
a = {}
a[3] = 1
a[0] = 2
a = {0:2, 3:1}
Python会自动更改我的插入顺序。由于Python声称字典是无序的集合,我不太理解为什么Python会保持这样的搜索顺序。Python是通过哈希表实现字典并存储另一个集合来进行索引排序吗?
希望我表述清楚了。
谢谢。
字典的顺序完全由对象的哈希函数(以及如果存在哈希冲突,则为插入顺序)确定。 整数的哈希值为其本身(至少在sys.maxint
范围内):
>>> hash(1)
1
(C)python 的实现会获取对象的哈希值并使用一些位来确定表中的索引。取决于字典的长度,需要多少位数才能将其确定下来。默认情况下,字典有8个可用槽,所以数字0
和8
会发生碰撞。我们可以如下所示:
>>> d1 = {}
>>> d1[0] = 'foo'
>>> d1[8] = 'bar'
>>> d1
{0: 'foo', 8: 'bar'}
>>>
>>> d2 = {}
>>> d2[8] = 'bar'
>>> d2[0] = 'foo'
>>> d2
{8: 'bar', 0: 'foo'}
由于在我们的字典中,0
和8
发生了碰撞,插入顺序似乎已经得到了维护。 0
占据了第一个可用的槽位(毕竟,无论从0
取多少位,你都会得到0
)。 8
也试图占据该槽位。然而,如果该槽位被占据,冲突解决机制便会介入,Python会在稍后的某个位置插入该值。
当然,如果您的字典恰好有超过5个元素,它将被调整大小(我认为是16,但不要引用我),0
和8
将不再发生碰撞...
>>> d1 = {x:x for x in range(1, 6)}
>>> d1[0] = 0
>>> d1[8] = 8
>>> d1
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8}
>>> d2 = {x:x for x in range(1, 6)}
>>> d2[8] = 8
>>> d2[0] = 0
>>> d2
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8}
注意,(排序的)顺序被保留了(不是插入顺序),这意味着每个整数都在哈希表中得到了其首选位置(没有冲突)。我认为当字典大约达到2/3时,它会被重新调整大小。
请注意,这仅仅是学术性质 -- Python规范并没有说这就是它的工作方式,因此它可能随时会发生变化。请不要依赖于这种行为。大部分内容可以从源代码注释和文档中获得...
hash(123456789101112)
-- 我认为只有当你超过sys.maxint
(在Cpython中)时,这才开始改变... - mgilsonhash(-1)
是另一个例外。 - Antti Haapala -- Слава Україні