In Expression for Static and DYnamic Arrays

[bearophile]

Jonathan M Davis:

> Because that would mean than in was O(n), whereas it's 
> generally assumed to be
> at least o(log n) (which is what you'd get in a balanced binary 
> tree such as
> red-black tree). AA's do it in O(1), so they're okay, but 
> dynamic arrays can't do better than O(n).

Time ago the built-in associative arrays of D used a search tree 
to solve hash collisions. But today they use linked lists for 
that purpose. This means to unlike the past today an adversary is 
able to create keys that turn AA search into O(n) searches. This 
is not theory.

Bye,
bearophile