what's going on below
>>> d = {0:0} >>> in d: ... del d[i] ... d[i+1] = 0 ... print(i) ... 0 1 2 3 4 5 6 7 >>> why iteration stop @ 8 without error?
reproducible on both python2.7 , python 3.5.
this behavior originates key algorithm in cpython static pydictkeyentry * lookdict(...) written in document:
the basic lookup function used operations. based on algorithm d knuth vol. 3, sec. 6.4. ... initial probe index computed hash mod table size (which equals 8).
at beginning of every loop, dict_next function called internally resolve address of next element. core of function reads:
value_ptr = &mp->ma_keys->dk_entries[i].me_value; mask = dk_mask(mp->ma_keys); // size of array stores 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 where i index of c array stores values. written above, initial index of key calculated hash(key)%table_size. other element in array set null since dict contains 1 element in test case.
given fact hash(i)==i if i int, memory layout of dict in example be:
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 a more interesting test case be:
def f(d): 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 to conclude, exiting condition of such loop
hash(new_key)%8<=hash(old_key)%8 