Internals of Python Dictionaries

Python uses open addressing in dictionaries! See, eg, Brandon Craig Rhodes’ The Mighty Dictionary.

I actually recall things learned in Algorithms: Design and Analysis. Awesome.

Some interesting points:

• Collisions are computationally expensive, so dictionaries resize themselves when partially full.
• Dictionaries only resize on insertion, not deletion.
• When dictionaries resize, their keys are reordered (based on the longer hash slice length).

Question: Why don’t ‘sparse’ dictionaries (where there are many dummies on the lookup path to a value) clean themselves up?

That is, if a backup slot needs to be used to store a value but the value occupying its preferred slot is eventually deleted, why isn’t the the value moved instead of just substituting a dummy value in the deleted value’s slot? (I suspect it’s a tradeoff favouring time over space.)

More on Stack Overflow.