Consistency

[FG via Digitalmars-d]

>> No, they were still O(n) worst case, for a single bucket with a degenerate binary tree.

What binary tree? I don't see any.

> I see. I was unable to hit this degenerate case in my testing code, but I guess that was possible. Thank you.

 From what I can see in druntime/rt/aaA.d, the bucket is chosen by dividing the key hash modulo the number of buckets. The number of buckets is a prime number (x in [31, 97, 389, 1543, ...]), so it is very unlikely to write a hash function that would give different results but the same (i % x) value. The most probable cause would therefore be a hash function implementation that gives the exact same hash for a prepared set of keys. Then you'd get the worse case scenario in which you have to walk a list and compare keys one-by-one in O(n).

But that's not a problem with the associative array implementation. It's a bad hash problem.