AA implementation algo should be mentioned

[Sean Kelly]

Frits van Bommel wrote:
> Sean Kelly wrote:
>> Double hashing is O(1) for inserts I think, but removals tend to be 
>> somewhat messy.
> 
> I don't think so. AFAIK, it's just a technique that attempts to avoid 
> the clustering effect that linear probing suffers from. However, in a 
> full table it can still take O(N) probes before an empty slot is found.
> Wikipedia seems to back me up on this: "Like all other forms of open 
> addressing, double hashing becomes linear as the hash table approaches 
> maximum capacity" (http://en.wikipedia.org/wiki/Double_hashing)

Could be, I suppose.  Though I'd have to tell a Data Structures 
professor I know that his proof is incorrect.  I suppose I could be 
mis-remembering the conclusion as well though.  Hm... it may have been 
based on particular growth conditions, like never letting the table get 
more than half full before a rehash.



Sean