Why does the following code behave so strangely? Python3.5 vs Python3.6 [duplicate]

Question

As the title says, why does the following code behave so strangely?

a = {
    0: 0
}
b = []

for i in a:
    del a[i]
    a[i + 1] = 0
    b.append(i)

print(b)

In Python3.6 it prints [0, 1, 2, 3, 4], whereas in Python3.5 it prints [0, 1, 2, 3, 4, 5, 6, 7]. Why?

Answer 1

In both cases the loop is not infinite for a simple reason: you create an iterator over the dict. This is simply an object that internally knows the size of the hashtable and keeps track of the index at which it arrived. When looping over this iterable it will simply check each slot in the hashtable to see if it is filled, and if it is filled it yields it otherwise it continues to increase the index.

Your dictionary never grows in size, it always has zero or one element so no reallocation of the hashtable is done and the iterator continues to the end of the hashtable.

Furthermore: small integer hash to themselves:

>>> print(*map(hash, range(10)))
0 1 2 3 4 5 6 7 8 9

This means that when you insert i+1 == 1 it is going to end up in slot 1 of the hashtable, and the iterator will find it in the next loop. Same happens with 2 etc. Until the hashcode is big enough to be "wrapped" over to the beginning of the hashtable. The iterator index does not wrap over, since it knows the size of the hashtable.

Python3.5 and python3.6 probably have different initial hashtable sizes (keep in mind that in python3.6 the dict class was reimplemented to be ordered).

---

Obviously all of this is an implementation detail. There is no language guarantee that the iterator acts like this, it's just a side-effect of the implementation. A future implementation might detect any change to the dict and raise an error instead of continuing.