为什么字典中的顺序是随意的?

我不明白如何遍历字典或在python中设置是由“任意”的顺序。

我的意思是,这是一种编程语言,所以语言中的所有内容都必须100%确定,正确吗? Python必须有一些决定select字典或集合的哪一部分的algorithm,第一,第二等等。

我错过了什么?

顺序不是任意的,而是取决于字典或集合的插入和删除历史logging,以及特定的Python实现。 对于这个答案的其余部分,对于'词典',你也可以阅读'设置'; 集合被实现为只有键和没有值的字典。

密钥被散列,并且哈希值被分配给dynamic表中的插槽(它可以根据需要增长或缩小)。 而且这个映射过程可能导致冲突,这意味着一个密钥将不得不根据已经存在的内容在下一个时隙中进行。

列出插槽中的内容循环,所以键按照它们当前驻留在表中的顺序列出。

'foo''bar'为例,假设表格大小为8个插槽。 在Python 2.7中, hash('foo')-4177197833195190597hash('bar')327024216814240868 。 模8,这意味着这两个键插在插槽3和4,然后:

 >>> hash('foo') -4177197833195190597 >>> hash('foo') % 8 3 >>> hash('bar') 327024216814240868 >>> hash('bar') % 8 4 

这通知他们的列表顺序:

 >>> {'bar': None, 'foo': None} {'foo': None, 'bar': None} 

除了3和4之外的所有插槽都是空的,在表格上循环显示第一个插槽3,然后插入第四个插槽,所以'foo''bar'之前列出。

然而, barbaz具有正好相隔8的散列值,因此映射到完全相同的时隙, 4

 >>> hash('bar') 327024216814240868 >>> hash('baz') 327024216814240876 >>> hash('bar') % 8 4 >>> hash('baz') % 8 4 

他们的顺序现在取决于哪个键被首先插入; 第二把钥匙将不得不被移动到下一个插槽:

 >>> {'baz': None, 'bar': None} {'bar': None, 'baz': None} >>> {'bar': None, 'baz': None} {'baz': None, 'bar': None} 

表顺序在这里不同,因为一个或另一个键被首先插入。

CPython(最常用的Python实现)使用的底层结构的技术名称是一个哈希表 ,它使用开放寻址。 如果你很好奇,并且足够了解C,那么看看所有(详细logging)细节的C实现 。 您还可以观看Brandon Rhodes在Pycon 2010演示文稿中关于CPython dict工作方式,或者阅读“ 美丽代码”的副本,其中包括由Andrew Kuchling编写的实现一章。

请注意,从Python 3.3起,也使用随机散列种子,使得散列冲突不可预知,以防止某些types的拒绝服务(攻击者通过引起大规模散列冲突呈现Python服务器无响应)。 这意味着给定字典的顺序依赖于当前Python调用的随机散列种子。

其他实现可以自由地为字典使用不同的结构,只要它们满足logging的Python接口,但是我相信到目前为止所有的实现都使用哈希表的变体。

CPython 3.6引入了一个新的 dict实现,它保持了插入顺序,并且更快,更有效地启动内存。 而不是保留一个大的稀疏表,其中每一行引用存储的散列值,键和值对象,新的实现添加一个较小的哈希数组 ,只引用密度表中的索引(一个只包含尽可能多的行键值对),并且它是按照顺序列出所包含项的密集表。 有关更多详细信息,请参阅Python-Dev的build议 。 请注意,这被认为是一个实现细节 ,Python-the-language没有指定其他实现必须保持顺序。

Python 2.7和更新版本还提供OrderedDict类 ,这是dict一个子类,它添加了一个额外的数据结构来logging键序。 以一些速度和额外的内存为代价,这个class级记得你以什么顺序插入了键; 列出键,值或项目将按顺序进行。 它使用存储在附加字典中的双向链接列表来有效地保持订单的最新状态。 请看Raymond Hettinger的文章概述了这个想法 。 请注意, settypes仍然是无序的。

如果你想要一个有序集,你可以安装oset包 ; 它适用于Python 2.5及以上。

这更多的是对Python 3.41的一个响应。


其他人是对的:不要依赖订单。 甚至不要假装有一个。

也就是说,有件事你可以依靠:

 list(myset) == list(myset) 

也就是说,订单是稳定的


了解为什么有一个感知秩序需要了解一些事情:

  • Python使用哈希集合

  • CPython的哈希集是如何存储在内存中的

  • 数字如何散列

从一开始:

哈希集合是一种以非常快的查找时间存储随机数据的方法。

它有一个支持数组:

 # AC array; items may be NULL, # a pointer to an object, or a # special dummy object _ _ 4 _ _ 2 _ _ 6 

我们将忽略特殊的虚拟对象,这只是为了使删除更容易处理,因为我们不会从这些集合中删除。

为了快速查找,你需要一些魔法来计算一个对象的散列值。 唯一的规则是两个相等的对象具有相同的散列。 (但是,如果两个对象具有相同的散列,则它们可以不相等)。

然后通过以数组长度取模来制作索引:

 hash(4) % len(storage) = index 2 

这使访问元素的速度非常快。

散列只是大部分故事,因为hash(n) % len(storage)hash(m) % len(storage)可以导致相同的数字。 在这种情况下,几种不同的策略可以尝试和解决冲突。 CPython在做复杂的事情之前使用“线性探测”9次,因此在查看其他地方之前,它会在插槽的左侧查找多达9个位置。

CPython的散列集是这样存储的:

  • 散列集不能超过2/3 。 如果有20个元素,并且后备数组的长度是30个元素,则后备存储将调整为更大。 这是因为你经常碰到小型的后援商店,而碰撞会把所有的东西放慢。

  • 后备库的大小调整为4,从8开始,除了resize为2(8,32,128,…)的大集(50k个元素)。

所以当你创build一个数组的时候,后备存储是8的长度。当它满5并且你添加一个元素的时候,它会简要的包含6个元素。 6 > ²⁄₃·8所以这会触发一个resize,而后备存储增加到32倍。

最后, hash(n)只返回数字(除了特殊的-1 )。


那么,让我们看看第一个:

 v_set = {88,11,1,33,21,3,7,55,37,8} 

len(v_set)是10,所以在添加所有项目后 ,后备存储至less为15(+1)。 2的相关功率是32.所以后台存储是:

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 

我们有

 hash(88) % 32 = 24 hash(11) % 32 = 11 hash(1) % 32 = 1 hash(33) % 32 = 1 hash(21) % 32 = 21 hash(3) % 32 = 3 hash(7) % 32 = 7 hash(55) % 32 = 23 hash(37) % 32 = 5 hash(8) % 32 = 8 

所以这些插入为:

 __ 1 __ 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __ 33 ← Can't also be where 1 is; either 1 or 33 has to move 

所以我们会期待一个像这样的命令

 {[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88} 

其中1或33个不在其他地方。 这将使用线性探测,所以我们要么有:

  ↓ __ 1 33 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __ 

要么

  ↓ __ 33 1 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __ 

你可能认为这个33是因为已经存在的而被置换的,但是由于在这个集合正在被build立时发生的大小调整,实际上并不是这样。 每次重build时,已经添加的项目都被有效地重新sorting。

现在你可以看到为什么

 {7,5,11,1,4,13,55,12,2,3,6,20,9,10} 

可能是为了。 有14个元素,所以后台存储至less是21 + 1,这意味着32:

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 

在前13个时隙中1到13个哈希。 20进入20号槽。

 __ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __ 

55在槽hash(55) % 32是23:

 __ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __ 

如果我们select了50,我们期望

 __ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __ 

你瞧,

 {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50} #>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20} 

pop很简单,通过外观的东西来实现:遍历列表并popup第一个。


这是所有的实现细节。

“任意”与“不确定”不同。

他们所说的是没有“在公共接口中”的字典迭代顺序的有用属性。 几乎可以肯定的是,迭代次序的许多属性完全由当前实现字典迭代的代码来确定,但是作者并不向你保证它们是你可以使用的。 这给了他们更多的自由来改变Python版本之间的这些属性(甚至只是在不同的运行条件下,或者在运行时完全随机),而不用担心程序会中断。

因此,如果你编写的程序依赖任何字典顺序的任何属性 ,那么你正在使用字典types“违反合同”,而且Python开发人员并不希望这种方式总能正常工作,即使它看起来可行现在当你testing它。 这基本上等同于依靠C中的“未定义的行为”

这个问题的其他答案是优秀的,写得很好。 操作程序询问我如何解释为什么“他们如何摆脱”或“为什么”。

Python文档说字典不是有序的,因为Python字典实现了抽象数据types 关联数组 。 像他们说的那样

绑定返回的顺序可以是任意的

换句话说,一个计算机科学的学生不能假定一个关联数组是有序的。 math中的集合也是如此

列出元素的顺序是不相关的

和计算机科学

一个集合是一个抽象的数据types,可以存储某些值,没有任何特定的顺序

使用哈希表来实现一个字典是一个有趣的实现细节 ,它与关联数组具有相同的属性,就顺序而言。

Python使用散列表来存储字典,所以在字典或其他使用散列表的可迭代对象中没有顺序。

但是关于散列对象中的项目索引,python会根据hashtable.c以下代码计算索引:

 key_hash = ht->hash_func(key); index = key_hash & (ht->num_buckets - 1); 

因此,由于整数的散列值是整数本身*索引是基于数字( ht->num_buckets - 1是一个常数),所以索引是按位计算的(ht->num_buckets - 1)和数字本身* (期望-1它的散列是-2),并为其他对象的散列值。

考虑以下使用散列表的set例子:

 >>> set([0,1919,2000,3,45,33,333,5]) set([0, 33, 3, 5, 45, 333, 2000, 1919]) 

对于33我们有:

 33 & (ht->num_buckets - 1) = 1 

这实际上是:

 '0b100001' & '0b111'= '0b1' # 1 the index of 33 

注意在这种情况下(ht->num_buckets - 1)8-1=70b111

1919

 '0b11101111111' & '0b111' = '0b111' # 7 the index of 1919 

而对于333

 '0b101001101' & '0b111' = '0b101' # 5 the index of 333 

有关Python哈希函数的更多细节,请阅读以下来自Python源代码的引用:

前面的主要细节:大多数散列scheme依赖于具有“良好”散列函数,在模拟随机性的意义上。 Python没有:它最重要的散列函数(对于string和整数)在常见情况下非常规则:

 >>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462] 

这不一定是坏的! 相反,在一个大小为2 ** i的表中,将低位i位作为初始表索引是非常快的,并且对于由连续的整数范围索引的字典完全没有冲突。 当键是“连续”string时大致相同。 所以这在一般情况下给出了比随机的好的行为,这是非常理想的。

OTOH当发生冲突时,填充散列表的连续片段的趋势使得一个好的冲突解决策略是至关重要的。 只考虑哈希码的最后一个比特也是脆弱的:例如,考虑列表[i << 16 for i in range(20000)]作为一组密钥。 由于ints是他们自己的散列码,并且这符合大小为2 ** 15的字典,所以每个散列码的最后15位都是0:它们映射到相同的表索引。

但是,迎合不寻常的情况不应该减慢平常的情况,所以我们只是拿最后一点而已。 剩下的就是碰撞解决scheme。 如果我们经常在第一次尝试中find我们要找的钥匙(事实certificate,我们通常会这么做 – 桌子的载重因子保持在2/3以下,所以我们对此感到满意),那么它保持最初的指标计算很便宜。


*类int的散列函数:

 class int: def __hash__(self): value = self if value == -1: value = -2 return value