0

I was wondering what happens when all slots get filled in a Python dictionary.

According to this Answer, python dictionaries use open addressing, and also they get initialized with 8 slots.

I would guess that after all 8 slots are filled, a new dictionary with more slots would be created, and all the entries rehashed and moved there

In order to test this, I wrote the following code:

dict={}

print(id(dict))
dict['A']=1
dict['B']=2
dict['C']=3
dict['D']=4
print(id(dict))
dict['E']=5
dict['F']=6
dict['G']=7
dict['H']=8
print(id(dict))
dict['I']=9
print(id(dict))

but I see that the id of the dictionary doesn't change after we get to the 9th entry:

140055316586712
140055316586712
140055316586712
140055316586712

I’m I interpreting the results right? From this I would deduct that the dictionary didn’t increase dynamically, but how if we only have 8 slots in initialization?

Fackelmann
  • 43
  • 6
  • 3
    The dictionary consists of a header that contains a pointer to the hash table. The header doesn't move when the hash table grows, so the id doesn't change. – Barmar Apr 05 '19 at 23:34
  • Ah! That certainly would make sense. Am I right then in my understanding on how they work? This is, a new hash table is created and every element is re-hashed there. – Fackelmann Apr 05 '19 at 23:36
  • 1
    Yes, that's correct. – Barmar Apr 05 '19 at 23:38
  • 1
    If there were no header, it would be difficult to have multiple variables referencing the same dictionary. When the dictionary is rehashed, it would have to find all the variables referencing it and update them. – Barmar Apr 05 '19 at 23:40

0 Answers0