In Expression for Static and DYnamic Arrays

bearophile bearophileHUGS at lycos.com
Fri Oct 12 10:56:43 PDT 2012


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


More information about the Digitalmars-d-learn mailing list