Hash array mapped trie
A hash array mapped trie[1] (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie[2].
Advantages of HAMTs
![[icon]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png){kind=small} | This section is empty. You can help by adding to it. (July 2010) |
Problems with HAMTs
Implementation of a HAMT involves the use of the population count function, which counts the number of ones in the binary representation of a number. This operation is available in many instruction set architectures (where it is sometimes called "CTPOP"), but it is only available in some high-level languages. Although population count can be implemented in software in O(1) time using a series of shift and add instructions, doing so may perform the operation an order of magnitude slower.
Implementations
The programming language Clojure uses a persistent variant of hash array mapped tries for its native hash map type.[3]
References
- ^ Bagwell, P. (2001) Ideal Hash Trees. Technical Report, 2001.
- ^ Bagwell, P. (2000) Fast And Space Efficient Trie Searches. Technical Report, 2000.
- ^ Java source file of Clojure's hash map type.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |