Consistency

[Steven Schveighoffer via Digitalmars-d]

On 2/16/15 1:23 AM, Daniel Murphy wrote:
> "bearophile"  wrote in message news:jufdlgyynxiwbqubbbkx at forum.dlang.org...
>
>> D associative arrays used to be O(1) amortized and O(n ln n) in worst
>> case.
>
> No, they were still O(n) worst case, for a single bucket with a
> degenerate binary tree.

IIRC, the AA code tried to make balanced trees, at least on rehash, but 
I thought it did so proactively on insertion too.

But in any case, the reason AA's are so slow is because the load factor 
is 4. As in, the AA will have 4x as many elements as buckets before it 
increases buckets. I've brought it up before. Typically you want to keep 
the number of elements per bucket near 1 for O(1) lookup.

-Steve