On Mar 18, 3:59 pm, Ninereeds <[EMAIL PROTECTED]> wrote: > Hrvoje Niksic wrote: > > This doesn't apply to Python, which implements dict storage as an > > open-addressed table and automatically (and exponentially) grows the > > table when the number of entries approaches 2/3 of the table size. > > Assuming a good hash function, filling the dict should yield amortized > > constant time for individual additions.
Isn't this average constant time rather than amortized? > OK. I obviously need to look up open-addressed tables. I thought this > was just, in effect, implicit linked listing - ie it still needs a > linear search to handle collisions, it just avoids the need for > explicitly stored link fields. Perhaps I'm mistaken. I don't think you are mistaken, but if I'm wrong I'd be grateful for a link to further details. Thanks -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
