finding items that occur more than once in a list

[Bryan Olson]

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