For Large Dictionaries Could One Use Separate Dictionaries Where Each Dictionary Covers an Interval of the Input Range?

[Roy Smith]

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.