finding items that occur more than once in a list

[Arnaud Delobelle]

On Mar 18, 3:59 pm, Ninereeds <stephenhorne... at aol.com> 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