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