AA implementation algo should be mentioned

[Frits van Bommel]

Sean Kelly wrote:
> Davidl at 126.com wrote:
>> without looking into phobos or join irc channel people would
>> never know what algo is used by AA. and that would make people
>> feel AA is not reliable, why not mention the algo used by AA
>> and the complexity on the page? i think that would make the
>> doc looks better
> 
> I personally love the C++ spec in this respect.  Everything in the 
> library is treated as an algorithm and complexity information is defined 
> for all operations.  However, I'm not sure that specifics about the 
> algorithm should be put into the D spec for AAs beyond that they must be 
> O(1) for lookups, O(N) for iteration via foreach, and possibly some 
> constraints on insert/remove performance (possibly amortized O(1) for 
> inserts and maybe O(N) for removals?).

I agree it would be nice if this were specified.

However, I don't think inserts are currently amortized O(1), are they? 
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.