On Monday, 16 February 2015 at 06:23:06 UTC, Daniel Murphy wrote:
"bearophile" wrote in message
news:[email protected]...
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?
