For Large Dictionaries Could One Use Separate Dictionaries Where Each Dictionary Covers an Interval of the Input Range?
roy at panix.com
Tue May 16 22:15:18 CEST 2006
In article <mailman.5762.1147805604.27775.python-list at python.org>,
<skip at pobox.com> wrote:
> Graham> Looking up a key in a dictionary is done in constant-time,
> Graham> i.e. it doesn't matter how large the dictionary is.
>Doesn't that depend on how many keys hash to the same value? For small
>dictionaries keeping the max keys that hash to the same value small isn't a
>huge problem. For large dictionaries (millions of keys) might you have some
>long chains? Or in an effort to reduce the chain length, wind up using so
>much virtual memory that you wind up wrecking performance by swapping?
If you're getting long hash chains, you're either using a bad hash
function, or your table isn't big enough.
More information about the Python-list