Arnaud Delobelle wrote: > Ninereeds 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?
This is expected amortized constant time. Is that really the same thing as average constant time? Hmmm... that's subtle. >> 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. The amortized doubling breaks that. > I don't think you are mistaken, but if I'm wrong I'd be grateful for a > link to further details. Arnaud Delobelle offered a good Wikipedia link, and for more background look up "amortized analysis. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list