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 the max keys that hash to the same value small isn't a > huge problem.
Hi Skip. On reflection, I guess I ought to have asked the OP what he meant by "large". :-) Probably asked for details on his use-case as well. Sure, collisions are a reality. The introductory comments in dictobject.c in the Python source [1] give good coverage of how these issues are handled in CPython. And, they make for great bedtime reading! :-) Regardless, I can't imagine that using multiple dictionaries would provide a sufficient speed-up for the vast majority of large dictionary use-cases. There are still swapping issues, plus the user-code overhead of managing the multiple dicts, plus the multiple lookups. If the only improvement is in collision reduction (which is questionable in the general case, since an unfortunate set of keys could result in numerous collisions even in a smaller database), then is the extra overhead really worth it? Still, it's just my opinion. If someone wants to post code and prove me wrong, I'll eat my hat and take my lickings. ;-) Best, Graham [1] http://svn.python.org/view/python/trunk/Objects/dictobject.c -- http://mail.python.org/mailman/listinfo/python-list
