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.