finding items that occur more than once in a list

[castironpi at gmail.com]

On Mar 18, 10:08 pm, Bryan Olson <fakeaddr... at nowhere.org> wrote:
> 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.

It's the same as expected constant time.

> >> 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.

>>> [ (i,hash(2**i)) for i in range( 0, 5000, 32 ) ]
[(0, 1), (32, 1), (64, 1), (96, 1), (128, 1), (160, 1), (192, 1),
(224, 1), (256
, 1), (288, 1), (320, 1), (352, 1), (384, 1), (416, 1), (448, 1),
(480, 1), (512
, 1), (544, 1), (576, 1), (608, 1), (640, 1), (672, 1), (704, 1),
(736, 1), (768
, 1), (800, 1), (832, 1), (864, 1), (896, 1), (928, 1), (960, 1),
(992, 1), (102
4, 1), (1056, 1), (1088, 1), (1120, 1), (1152, 1), (1184, 1), (1216,
1), (1248,
1), (1280, 1), (1312, 1), (1344, 1), (1376, 1), (1408, 1), (1440, 1),
(1472, 1),
 (1504, 1), (1536, 1), (1568, 1), (1600, 1), (1632, 1), (1664, 1),
(1696, 1), (1

Not so farfetched, all.  Don't forget big-theta and big-omega.