Python字典实现细节

Question

Python字典实现细节

11

我有一个关于Python字典实现的问题。

似乎Python会为所有键维护一个搜索顺序，例如如果您执行以下操作：

a = {}
a[3] = 1
a[0] = 2

a = {0:2, 3:1}

Python会自动更改我的插入顺序。由于Python声称字典是无序的集合，我不太理解为什么Python会保持这样的搜索顺序。Python是通过哈希表实现字典并存储另一个集合来进行索引排序吗？

希望我表述清楚了。

谢谢。

- user3786609

PyPy的字典可能是有序的。 - jfs

我将此标记为重复问题，因为您的具体问题应该已经在回答中得到了充分解答，尽管我意识到问题并不完全匹配。请查看重复问题侧边栏中的“相关问题”以获取更多信息。 - Veedrac

2个回答

1

字典索引顺序仅是字典实现的结果，不能依赖于它。确切地说，Python不会改变您插入项的顺序（因为这仅被定义为您向字典中插入项的顺序），但迭代顺序没有保障。当Python创建一个字典时，它会为8个键值对（我想）创建足够的空间。对于空字典，没有填充任何内容。每当您将一个项放入字典中时，Python会获取该键的哈希值，并根据键的哈希决定索引将在何处。如果您希望迭代顺序与插入顺序相同，请查看 ordereddict。

- Cody Piersall

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mgilson · Accepted Answer

字典的顺序完全由对象的哈希函数（以及如果存在哈希冲突，则为插入顺序）确定。整数的哈希值为其本身（至少在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规范并没有说这就是它的工作方式，因此它可能随时会发生变化。请不要依赖于这种行为。大部分内容可以从源代码注释和文档中获得...