For Large Dictionaries Could One Use Separate Dictionaries Where Each Dictionary Covers an Interval of the Input Range?
skip at pobox.com
skip at pobox.com
Tue May 16 20:48:14 EDT 2006
bob> If you have the same number of entries as buckets, and you have a
bob> good hash function, then if you have n buckets your longest chain
bob> should have length around ln(n). The average length of a nonempty
bob> bucket would be somewhere around 1 1/2.
Yes, and it achieves that nice short chain length by consuming gobs of
memory. A dictionary with 10**7 keys is going to chew up lots of memory.
There's nothing particularly magical about dictionaries in this respect.
They are good examples of a classic time-space tradeoff.
Skip
More information about the Python-list
mailing list