Consistency

[Andrei Alexandrescu via Digitalmars-d]

On 2/15/15 10:45 AM, bearophile wrote:
> Meta:
>
>> Oh, whoops. I mixed up average-case complexity with worst-case.
>> Although, isn't lookup O(n) in the worst case for hash tables?
>
> D associative arrays used to be O(1) amortized and O(n ln n) in worst
> case. Now they are O(1) amortized and O(n) worst case. And for an
> adversary it's not too much hard to find and hit that O(n) case.

I remember associative arrays were a lot slower and bigger before. -- Andrei