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 232.

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?


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.