在迭代期间修改dict

Question

下面发生了什么

>>> d = {0:0}
>>> for i in d:
...     del d[i]
...     d[i+1] = 0
...     print(i)
...     
0
1
2
3
4
5
6
7
>>> 

为什么迭代在没有任何错误的情况下停在8？

可在python2.7和python 3.5上重现.

Answer 1

dict中键表的初始大小为8个元素.所以0... 7设置第1到第8个元素,8再次设置第1个元素,结束循环.

来源:Objects/dictobject.c

/*PyDict_MINSIZE_COMBINED是任何新的非拆分字典的起始大小.8允许dicts不超过5个活动条目; 实验表明,这足以满足大多数dicts(主要包括为传递关键字参数而创建的通常小的dicts).使这8而不是4减少了大多数字典的调整大小,没有任何显着的额外内存使用.*/

#define PyDict_MINSIZE_COMBINED 8

Answer 2

此行为源自文档中static PyDictKeyEntry * lookdict(...)编写的cpython中的键查找算法:

所有操作使用的基本查找功能.这是基于Knuth Vol的算法D. 3,Sec.6.4....初始探测索引计算为表大小的哈希模式(最初等于8).

在每个for循环的开始处,在dict_next内部调用该函数以解析下一个元素的地址.该函数的核心内容如下:

value_ptr = &mp->ma_keys->dk_entries[i].me_value;
mask = DK_MASK(mp->ma_keys); // size of the array which stores the key values (ma_keys)
while (i <= mask && *value_ptr == NULL) { // skip NULL elements ahead 
    value_ptr = (PyObject **)(((char *)value_ptr) + offset);
    i++;
}
if (i > mask)
    return -1; // raise StopIteration 

其中i是实际存储值的C数组的索引.如上所述,密钥的初始索引是从中计算出来的hash(key)%table_size.数组中的另一个元素都设置为,NULL因为dict在测试用例中只包含一个元素.

鉴于hash(i)==iif i是一个int,你的例子中dict的内存布局将是:

1st iter: [0,   NULL,NULL,NULL,NULL,NULL,NULL,NULL]; i=0
2nd iter: [NULL,1   ,NULL,NULL,NULL,NULL,NULL,NULL]; i=1
...
8th iter: [NULL,NULL,NULL,NULL,NULL,NULL,NULL,7   ]; i=7

一个更有趣的测试用例是:

def f(d):
  for i in d:
    del d[i]
    print hash(i)%8
    d[str(hash(i))]=0
f({0:0})       # outputs 0,1,6
f({'hello':0}) # outputs 5,7
f({'world':0}) # outputs 1

总之,这种循环的退出条件是

hash(new_key)%8<=hash(old_key)%8