为什么在对集合进行迭代时添加和移除集合时会得到这么多次迭代？

Question

试图理解 Python for 循环，我认为这会给出一次迭代的结果 {1}，或者只是陷入无限循环，具体取决于它是否进行迭代就像在 C 或其他语言中一样。但实际上两者都没有。

>>> s = {0}
>>> for i in s:
...     s.add(i + 1)
...     s.remove(i)
...
>>> print(s)
{16}

为什么要进行16次迭代？结果{16}从何而来？

这是使用 Python 3.8.2。在 pypy 上它会产生预期的结果 {1}.

Answer 1

来自 python3 文档：

Code that modifies a collection while iterating over that same collection can be tricky to get right. Instead, it is usually more straight-forward to loop over a copy of the collection or to create a new collection:

迭代一个副本

s = {0}
s2 = s.copy()
for i in s2:
     s.add(i + 1)
     s.remove(i)

应该只迭代 1 次

>>> print(s)
{1}
>>> print(s2)
{0}

编辑：这种迭代的一个可能原因是因为集合是无序的，导致某种堆栈跟踪之类的事情。如果你用一个列表而不是一个集合来做，那么它就会以 s = [1] 结束，因为列表是有序的，所以 for 循环将从索引 0 开始，然后移动到下一个索引，发现没有一个，并退出循环。

Answer 2

我认为这与 python 中集合的实际实现有关。集合使用散列 table 来存储它们的项目，因此遍历集合意味着遍历其散列 table 的行。

当您迭代并将项目添加到您的集合时，将创建新的哈希值并将其附加到哈希值 table 直到您达到数字 16。此时，下一个数字实际上被添加到散列 table 而不是结束。由于您已经迭代了 table 的第一行，因此迭代循环结束。

我的回答是基于一个类似的问题，它实际上显示了这个完全相同的例子。我真的建议阅读它以获取更多详细信息。

Answer 3

Python 不承诺此循环何时（如果有的话）结束。在迭代期间修改集合会导致跳过元素、重复元素和其他怪异现象。 切勿依赖此类行为。

我要说的都是实施细节，如有更改，恕不另行通知。如果您编写依赖于其中任何一个的程序，您的程序可能会在 Python 实现和除 CPython 3.8.2.

之外的任何版本组合上中断

为什么循环在 16 处结束的简短解释是，16 是恰好位于比前一个元素更低的哈希 table 索引处的第一个元素。完整的解释如下。

Python 集合的内部散列 table 大小始终为 2 的幂。对于大小为 2^n 的 table，如果没有发生冲突，元素将存储在散列中对应于其散列的 n 个最低有效位的位置 table。你可以在 set_add_entry:

中看到这个实现

mask = so->mask;
i = (size_t)hash & mask;

entry = &so->table[i];
if (entry->key == NULL)
    goto found_unused;

大多数小 Python 整数散列到自己；特别是，您测试中的所有整数都对自己进行散列。您可以在 long_hash 中看到它的实现。由于您的集合从不包含两个在其哈希值中具有相同低位的元素，因此不会发生冲突。

A Python 集合迭代器跟踪其在集合中的位置，并在集合的内部散列 table 中使用简单的整数索引。当请求下一个元素时，迭代器从该索引开始在散列 table 中搜索填充的条目，然后将其存储的索引设置为紧跟在找到的条目和 returns 条目的元素之后。您可以在 setiter_iternext:

中看到

while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
    i++;
si->si_pos = i+1;
if (i > mask)
    goto fail;
si->len--;
key = entry[i].key;
Py_INCREF(key);
return key;

您的集合最初以大小为 8 的哈希 table 和指向哈希 table 中索引 0 处的 0 int 对象的指针开始。迭代器也位于索引 0。当你迭代时，元素被添加到散列 table，每个元素都在下一个索引处，因为这是他们的散列说要放置它们的地方，而且它总是迭代器查看的下一个索引.移除的元素有一个虚拟标记存储在它们的旧位置，用于冲突解决目的。您可以在 set_discard_entry:

中看到它的实现

entry = set_lookkey(so, key, hash);
if (entry == NULL)
    return -1;
if (entry->key == NULL)
    return DISCARD_NOTFOUND;
old_key = entry->key;
entry->key = dummy;
entry->hash = -1;
so->used--;
Py_DECREF(old_key);
return DISCARD_FOUND;

当 4 添加到集合中时，集合中的元素和虚拟元素的数量变得足够多 set_add_entry 触发哈希 table 重建，调用 set_table_resize:

if ((size_t)so->fill*5 < mask*3)
    return 0;
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

so->used 是散列 table 中填充的非虚拟条目的数量，即 2，因此 set_table_resize 接收 8 作为其第二个参数。基于此，set_table_resize decides 新散列 table 大小应为 16:

/* Find the smallest table size > minused. */
/* XXX speed-up with intrinsics */
size_t newsize = PySet_MINSIZE;
while (newsize <= (size_t)minused) {
    newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
}

它重建大小为 16 的散列 table。所有元素仍然在新散列 table 中的旧索引处结束，因为它们的散列中没有设置任何高位.

随着循环的继续，元素不断被放置在迭代器将查找的下一个索引处。另一个哈希 table 重建被触发，但新的大小仍然是 16.

当循环添加 16 作为元素时，模式中断。没有用于放置新元素的索引 16。 16 的最低 4 位是 0000，将 16 放在索引 0 处。此时迭代器存储的索引是 16，当循环向迭代器请求下一个元素时，迭代器看到它已经过了哈希 table.

迭代器此时终止循环，集合中只留下16。

Answer 4

Python 设置一个不记录元素位置或插入顺序的无序集合。 python 集中的任何元素都没有附加索引。所以他们不支持任何索引或切片操作。

所以不要指望您的 for 循环会按定义的顺序工作。

为什么要迭代16次？

user2357112 supports Monica已经说明了主要原因。这里，换个思路。

s = {0}
for i in s:
     s.add(i + 1)
     print(s)
     s.remove(i)
print(s)

当你运行这段代码时，它会给你输出：

当我们像循环或打印集合一样访问所有元素时，必须有一个预定义的顺序来遍历整个集合。因此，在上一次迭代中，您会看到顺序从 {i,i+1} 更改为 {i+1,i}。

最后一次迭代后碰巧 i+1 已经遍历所以循环退出。

有趣的事实： 使用任何小于 16 的值，除了 6 和 7 总是会得到结果 16。

为什么在对集合进行迭代时添加和移除集合时会得到这么多次迭代？

Why do I get this many iterations when adding to and removing from a set while iterating over it?

python

python-internals