AA implementation algo should be mentioned

[Sean Kelly]

Frits van Bommel wrote:
> 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? 

Oops, you're right.  They're typically O(N) with a best case (omega?) of 
1.  Double hashing is O(1) for inserts I think, but removals tend to be 
somewhat messy.

> 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 :-)


Sean