On 02/11/2011 10:35 AM, spir wrote: > D's builtin AAs seem /very/ fast > on key access. You'd probably have a hard time even approaching their > performance using whatever kind of tree (or rather, of trie).
That is expected. D AAs are hash tables, meaning that they provide O(1) complexity for element access; compared to the O(log N) complexity of binary trees.
For completeness: adding elements is still O(1) for a hash table; compared to O(N log N) of a tree.
Ali