python - 为什么在迭代时添加到集合和从集合中删除时会得到这么多的迭代？

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

Python 没有 promise 这个循环何时(如果有的话)结束。在迭代过程中修改集合可能会导致元素被跳过、元素重复和其他奇怪的现象。 永远不要依赖这种行为。

我要说的一切都是实现细节，如有更改，恕不另行通知。如果您编写的程序依赖于其中任何一个，则您的程序可能会因 Python 实现和版本的任何组合而中断，而不是 CPython 3.8.2。

为什么循环在 16 结束的简短解释是 16 是第一个元素，它碰巧放置在比前一个元素更低的哈希表索引处。完整的解释如下。

Python 集合的内部哈希表大小始终为 2 的幂。对于大小为 2^n 的表，如果没有发生冲突，元素将存储在哈希表中与其哈希的 n 个最低有效位相对应的位置。你可以在 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 中看到这个实现.由于您的集合从不包含哈希中具有相同低位的两个元素，因此不会发生冲突。

Python 集合迭代器使用集合内部哈希表中的简单整数索引来跟踪其在集合中的位置。当请求下一个元素时，迭代器在哈希表中从该索引开始搜索填充的条目，然后将其存储的索引设置为紧跟在找到的条目之后并返回条目的元素。你可以在 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 的哈希表和指向 0 的指针开始。哈希表中索引 0 处的 int 对象。迭代器也位于索引 0 处。当您迭代时，元素被添加到哈希表中，每个元素都在下一个索引处，因为它们的哈希表示将它们放在那里，并且它始终是迭代器查看的下一个索引。删除的元素在其旧位置存储了一个虚拟标记，用于解决冲突。你可以看到在 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触发哈希表重建，调用 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是哈希表中填充的非虚拟条目的数量，即 2，因此 set_table_resize接收 8 作为它的第二个参数。基于此， set_table_resize decides新的哈希表大小应为 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 的哈希表。所有元素仍以新哈希表中的旧索引结束，因为它们的哈希值中没有设置任何高位。

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

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

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