Consistency

[via Digitalmars-d]

On Monday, 16 February 2015 at 06:23:06 UTC, 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.

Java 7 changed its HashMap implementation to use TreeMap (red 
black search tree) instead of LinkedList for its buckets, if the 
key can be sorted. That puts the worst case lookup time from O(n) 
to O(log n) for sortable keys. Maybe that's worth considering for 
AAs?