Hash array mapped trie — это ассоциативный контейнер, который обладает свойствами хэш таблиц и trie. Операции вставки пары ключ-значение и поиск по ключу — О(1) операции. Про trie на хабре уже [писали][1]. [Читать дальше →][2]

[1]: http://habrahabr.ru/post/111874
[2]: http://habrahabr.ru/post/266861/#habracut