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
