AA implementation algo should be mentioned

[Frits van Bommel]

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)

> Frits van Bommel wrote:
>> IIRC the Phobos implementation uses a hash table with binary trees for 
>> collision handling, which would mean /average/ O(1) for "good" 
>> toHash() implementations, but worst-case O(log N) (for "bad" toHash()s).
>> Also, that would mean removals are currently O(log N) as well, but 
>> specifying O(N) would allow other standard library implementations to 
>> use linked lists instead of binary trees so perhaps that's for the best.
> 
> Yup, which is correct IMO.  There should be no restriction on 
> implementation other than that some form of hashing is desired :-)

Right, I just wanted to mention that. (IIRC that's also the philosophy 
the C++ standard follows on this point)