What is the space complexity of a Python dictionary?

Question

If python dictionaries are essentially hash tables and the length of hashes used in the python dictionary implementation is 32 bits, that would mean that regardless of the number of key-value pairs that actually exist in any given dictionary the size of the dictionary is static and fixed with a length of 2³².

Such an implementation would be a waste of memory so I'm assuming this isn't the actual space complexity. How is a python dictionary actually implemented and what is its space complexity?

Answer 1

Space complexity is a property of algorithms, not of data-structures. And your assumption that the dictionary has a (large) fixed size would imply that it is O(1).

It doesn't start with the maximum size, but instead uses some fraction of the hash to index a smaller allocation. When it grows too large, it will re-hash the contents into a larger allocation.