Michael Peuser mpeuser at web.de
Thu Sep 11 16:29:51 CEST 2003

"Graham Fawcett" <fawcett at teksavvy.com

> I'm willing to be wrong twice, honestly I am! But I'm pretty sure it's
> constant time. B-tree searches are log2(n), but dicts aren't trees.
> Can't find a real reference, but the Timbot spoke here:
> http://mail.python.org/pipermail/tutor/2002-August/016800.html
> If I'm wrong on this one, I'll wear the Python Dunce Cap for a week,
> while repeating my corrected lessons!
I am pretty sure you will not have to! It is generally very difficult to
compute the mean access time to a hash. It totally depends on the size of
the internal hash table allocated as to the number of elements you store
there. In Perl there is trick to manipulate that (i.e. to increase it
appropriately when you expect e.g. some 100.000 entries). I don't know
whether this is possible in (C)Python, according to which algorithm the
initial size is computed, and when or if the table is reconfigured (which
would be a major undertaking btw). Any info someone?

Apart from that, you will generally find the value to your key with the
first access if the table is decently dimensioned.

Michael P

More information about the Python-list mailing list