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

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 t

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

Roy> If you're getting long hash chains, you're either using a bad hash Roy> function, or your table isn't big enough. Sure. The original poster said something about 10 million keys I think. Unless the key distribution is amazingly fortuitous and the number of unique values is small, the

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

If you have the same number of entries as buckets, and you have a good hash function, then if you have n buckets your longest chain should have length around ln(n). The average length of a nonempty bucket would be somewhere around 1 1/2. -- http://mail.python.org/mailman/listinfo/python-list

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

In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> 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

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

On 5/16/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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 th

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

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.

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

Casey Hawthorne wrote: > For Large Dictionaries Could One Use Separate Dictionaries Where Each > Dictionary Covers an Interval of the Input Range? One Could, But Why? :-) You wouldn't see any performance improvements. Looking up a key in a dictionary is done in constant-time, i.e.

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

For Large Dictionaries Could One Use Separate Dictionaries Where Each Dictionary Covers an Interval of the Input Range? You would need to know something of the input range and its uniformity! Self-balancing between dictionaries for separate dictionaries? -- Regards, Casey -- http