我不明白如何通过“任意”顺序循环遍历字典或在 python 中设置。
我的意思是，它是一种编程语言，所以语言中的所有内容都必须 100% 确定，对吗？Python 必须有某种算法来决定选择字典或集合的哪一部分，第一，第二等等。
我错过了什么？
问问题
19716 次
5 回答
255
注意：
dict此答案是在 Python 3.6 中更改类型的实现之前编写的。此答案中的大多数实现细节仍然适用，但字典中键的列出顺序不再由哈希值确定。设置实现保持不变。
顺序不是任意的，而是取决于字典或集合的插入和删除历史，以及具体的 Python 实现。对于此答案的其余部分，对于“字典”，您还可以阅读“设置”；集合被实现为只有键而没有值的字典。
键被散列，散列值被分配给动态表中的槽（它可以根据需要增长或缩小）。并且该映射过程可能会导致冲突，这意味着必须根据已经存在的内容将密钥插入下一个插槽。
列出内容在插槽上循环，因此键按照它们当前在表中的顺序列出。
以键'foo'和'bar'为例，假设表大小为 8 个插槽。在 Python 2.7 中，hash('foo')是-4177197833195190597，hash('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，然后列出插槽 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 的 Pycon 2010 演示文稿，了解 CPythondict的工作原理，或者获取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 概述该想法的帖子。OrderedDict对象还有其他优点，例如可重新排序。
如果你想要一个有序的集合，你可以安装oset包；它适用于 Python 2.5 及更高版本。
于 2013-03-18T15:01:12.857 回答
39
这更像是对Python 3.41 A set在作为副本关闭之前的回应。
其他人是对的：不要依赖顺序。甚至不要假装有一个。
也就是说，您可以依靠一件事：
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 full。如果有 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) % 32，即 23：
__ 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看起来很简单：它遍历列表并弹出第一个。
这是所有实现细节。
于 2014-09-29T12:13:10.043 回答
17
“任意”与“不确定”不同。
他们的意思是“在公共接口中”没有字典迭代顺序的有用属性。几乎可以肯定，迭代顺序的许多属性完全由当前实现字典迭代的代码决定，但作者并没有向您保证它们是您可以使用的。这使他们可以更自由地在 Python 版本之间更改这些属性（或者甚至只是在不同的操作条件下，或者在运行时完全随机），而不必担心您的程序会中断。
因此，如果您编写的程序完全依赖于字典顺序的任何属性，那么您就是在“违反使用字典类型的合同”，并且 Python 开发人员并不承诺这将始终有效，即使它看起来有效现在当你测试它时。它基本上相当于依赖 C 中的“未定义行为”。
于 2013-11-03T01:47:49.693 回答
5
Python 使用哈希表来存储字典，因此字典或其他使用哈希表的可迭代对象中没有顺序。
但是关于哈希对象中hashtable.c项目的索引，python根据以下代码计算索引：
key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);
因此，由于整数的哈希值是整数本身*索引是基于数字（ht->num_buckets - 1是一个常数）所以按位(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 位作为初始表索引非常快，并且对于由连续范围的 int 索引的 dicts 完全没有冲突。当键是“连续的”字符串时，情况大致相同。因此，这在常见情况下提供了优于随机的行为，这是非常可取的。
OTOH，当发生冲突时，填充哈希表的连续切片的趋势使得良好的冲突解决策略至关重要。只取哈希码的最后 i 位也是易受攻击的：例如，将列表
[i << 16 for i in range(20000)]视为一组键。 由于整数是它们自己的哈希码，并且这适合大小为 2**15 的字典，因此每个哈希码的最后 15 位都是 0：它们都映射到同一个表索引。但迎合不寻常的情况不应该减慢通常的情况，所以无论如何我们只取最后 i 位。剩下的工作由碰撞解决来完成。如果我们通常在第一次尝试时就找到了我们正在寻找的密钥（事实证明，我们通常会这样做——表加载因子保持在 2/3 以下，所以我们的胜算非常大），那么它保持初始索引计算便宜是最有意义的。
* 类的哈希函数int：
class int:
def __hash__(self):
value = self
if value == -1:
value = -2
return value
于 2015-05-29T21:40:14.520 回答