为什么字典中的顺序和设置是任意的？

Question

我不明白如何通过'任意'顺序完成字典或python中的循环.

我的意思是,它是一种编程语言,所以语言中的所有内容都必须100%确定,对吗？Python必须有某种算法来决定选择字典或集合的哪一部分,第一,第二等等.

我错过了什么？

Answer 1

顺序不是任意的,但取决于字典或集的插入和删除历史,以及特定的Python实现.对于本答案的其余部分,对于"词典",您还可以阅读"设置"; 集合实现为只包含键而没有值的字典.

对密钥进行哈希处理,并将哈希值分配给动态表中的槽(它可以根据需要增长或缩小).并且该映射过程可能导致冲突,这意味着必须根据已经存在的内容在下一个时隙中插入密钥.

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

带钥匙'foo'和'bar',例如,和让我们假设该表大小为8个时隙.在Python 2.7中,hash('foo')是-4177197833195190597,hash('bar')是327024216814240868.Modulo 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,然后插入插槽4,因此'foo'在前面列出'bar'.

bar和baz,但是,具有恰好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,请查看所有(详细记录的)详细信息的C实现.您还可以观看Brandon Rhodes关于CPython如何dict工作的Pycon 2010演示文稿,或者阅读Beautiful Code的副本,其中包括Andrew Kuchling撰写的有关实现的章节.

请注意,从Python 3.3开始,也会使用随机散列种子,使得散列冲突无法预测,以防止某些类型的拒绝服务(攻击者通过引发大规模散列冲突而使Python服务器无响应).这意味着给定字典的顺序也取决于当前Python调用的随机散列种子.

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

CPython 3.6引入了一种新的 dict实现,可以维护插入顺序,并且启动速度更快,内存效率更高.新实现不是保留每个行引用存储的哈希值以及键和值对象的大型稀疏表,而是添加一个较小的哈希数组,该数组仅引用密集表中的索引(一个只包含与实际数量相同的行数)键值对,并且它是密集的表,恰好按顺序列出包含的项.有关更多详细信息,请参阅Python-Dev的提案.请注意,在Python 3.6中,这被认为是一个实现细节,Python-the-language没有指定其他实现必须保留顺序.这在Python 3.7中有所改变,其中这个细节被提升为语言规范 ; 要使任何实现与Python 3.7或更新版本正确兼容,它必须复制此顺序保留行为.

Python 2.7和更新版本还提供了一个OrderedDict类,它的子类dict添加了一个额外的数据结构来记录键顺序.以某种速度和额外内存为代价,这个类会记住你插入键的顺序; 列表键,值或项目将按此顺序执行.它使用存储在附加字典中的双向链表来有效地保持订单的最新状态.请参阅Raymond Hettinger的帖子,概述这个想法.请注意,该set类型仍然是无序的.

如果你想要一个有序的套装,你可以安装oset包装 ; 它适用于Python 2.5及更高版本.

Answer 2

这更像是对Python 3.41 A集的响应,它在作为副本关闭之前.

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

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

list(myset) == list(myset)

也就是说,订单是稳定的.

理解为什么存在感知的顺序需要理解一些事情:

• Python使用哈希集,

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

• 数字是如何得到的

从一开始:

一个哈希集合是存储随机数据与真快,查找时间的方法.

它有一个支持数组:

# A C 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开始,除了大集(50k元素),其大小调整为2:(8,32,128,...).

因此,当您创建一个数组时,后备存储的长度为8.当它已满5并且您添加了一个元素时,它将暂时包含6个元素.6 > ²??·8所以这会触发调整大小,后备存储会翻两番到32.

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

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

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

len(v_set)是10,所以在添加所有项目后,后备存储至少为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是因为1已经存在而被替换的那个,但是由于在构建集合时发生的调整大小,实际上并非如此.每次重建集合时,已经添加的项目都会被有效地重新排序.

现在你可以看到原因了

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

可能是有序的.有14个元素,因此后备存储至少为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) % 3223:

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

如果我们选择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 通过事物的外观非常简单地实现:它遍历列表并弹出第一个列表.

这是所有实现细节.

Answer 3

"任意"与"不确定"不同.

他们所说的是"在公共接口中"没有字典迭代顺序的有用属性.几乎可以肯定,迭代顺序的许多属性完全由当前实现字典迭代的代码确定,但作者并不认为它们可以作为您可以使用的东西.这使他们可以更自由地在Python版本之间更改这些属性(甚至只是在不同的操作条件下,或者在运行时完全随机),而不必担心程序会中断.

因此,如果你编写一个依赖于所有字典顺序的任何属性的程序,那么你正在"违反使用字典类型的合同",并且Python开发人员不承诺这将始终有效,即使它似乎工作现在当你测试它.它基本上相当于依赖于C中的"未定义行为".

Answer 4

这个问题的其他答案都非常好而且写得很好.OP询问"我如何"解释为"他们如何逃脱"或"为什么".

Python文档说字典不是有序的,因为Python字典实现了抽象数据类型 关联数组.正如他们所说

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

换句话说,计算机科学专业的学生不能假设关联数组是有序的.数学中的集合也是如此

列出元素的元素的顺序是无关紧要的

和计算机科学

set是一种抽象数据类型,可以存储某些值,而不需要任何特定的顺序

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

Answer 5

Python使用哈希表来存储字典,因此在字典或其他使用哈希表的可迭代对象中没有顺序.

但是,在一个哈希对象有关的项目指标,蟒蛇计算基于下面的代码索引中hashtable.c:

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

因此,由于整数的哈希值是整数本身^*,索引是基于数字(ht->num_buckets - 1是一个常数)所以索引是由Bitwise和之间(ht->num_buckets - 1)的数字本身计算的^*(期望为-1,它的哈希值为-2) ),以及其他具有哈希值的对象.

考虑以下set使用hash-table的示例:

>>> 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=7或0b111.

并为1919:

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

并为333:

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

有关python哈希函数的更多详细信息,请阅读python源代码中的以下引用:

未来的主要细微之处:在模拟随机性的意义上,大多数哈希方案依赖于具有"良好"哈希函数.Python没有:它最重要的哈希函数(对于字符串和整数)在常见情况下是非常规则的:

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

这不一定是坏事!相反,在大小为2**i的表中,将低位i位作为初始表索引是非常快的,并且对于由连续的整数范围索引的dicts,根本没有冲突.当键是"连续"字符串时,大致相同.因此,这在常见情况下提供了比随机更好的行为,这是非常理想的.

OTOH,当发生冲突时,填充哈希表的连续切片的趋势使得良好的冲突解决策略成为关键.仅取哈希码的最后一位也很容易受到攻击:例如,将列表[i << 16 for i in range(20000)]视为一组键. 由于int是他们自己的哈希码,并且这适合于大小为2**15的dict,每个哈希码的最后15位都是0:它们都映射到相同的表索引.

但迎合不寻常的情况不应该减慢通常的情况,所以我们无论如何都要拿最后的i位.其余部分取决于碰撞解决方案.如果我们通常在第一次尝试时找到我们正在寻找的密钥(事实证明,我们通常会这样做 - 表负载系数保持在2/3以下,因此可能性对我们有利),然后它最有意义的是保持初始索引计算的便宜.

_{*类的哈希函数int:}

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