0

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?

MShakeG
  • 127
  • 4

1 Answers1

4

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.

Caleth
  • 10,519
  • 2
  • 23
  • 35