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.[1] It is a refined version of the more general notion of a hash tree.
Operation[edit]
A HAMT is an array mapped trie where the keys are first hashed to ensure an even distribution of keys and a constant key length.
In a typical implementation of HAMT's array mapped trie, each node contains a table with some fixed number N of slots with each slot containing either a nil pointer or a pointer to another node. N is commonly 32. As allocating space for N pointers for each node would be expensive, each node instead contains a bitmap which is N bits long where each bit indicates the presence of a non-nil pointer. This is followed by an array of pointers equal in length to the number of ones in the bitmap, (its Hamming weight).
Advantages of HAMTs[edit]
The hash array mapped trie achieves almost hash table-like speed while using memory much more economically. Also, a hash table may have to be periodically resized, an expensive operation, whereas HAMTs grow dynamically. Generally, HAMT performance is improved by a larger root table with some multiple of N slots; some HAMT variants allow the root to grow lazily[1] with negligible impact on performance.
Implementation details[edit]
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, but it is available in only 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.[citation needed]
Implementations[edit]
The programming languages Clojure,[2] Scala, and Frege[3] use a persistent variant of hash array mapped tries for their native hash map type. The Haskell library "unordered-containers" uses the same to implement persistent map and set data structures.[4] Another Haskell library "stm-containers" adapts the algorithm for use in the context of Software Transactional Memory.[5] A Javascript HAMT library [6] based on the Clojure implementation is also available. The Rubinius[7] implementation of Ruby includes a HAMT, mostly written in Ruby but with 3[8] primitives. Large maps in Erlang use a HAMT representation internally since release 18.0.[9] The Pony programming language uses a HAMT for the hash map in its persistent collections package.[10]
The concurrent lock-free version[11] of the hash trie called Ctrie is a mutable thread-safe implementation which ensures progress. The data-structure has been proven to be correct[12] - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties.
References[edit]
- ^ a b c Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
- ^ Java source file of Clojure's hash map type.
- ^ Frege source file of Frege's hash map type.
- ^ Johan Tibell, A. Announcing unordered-containers 0.2
- ^ Nikita Volkov, Announcing the "stm-containers" library, 2014
- ^ Javascript HAMT library and source
- ^ Ruby source file of Rubinius's HAMT
- ^ [1]
- ^ [2]
- ^ [3]
- ^ Prokopec, A. Implementation of Concurrent Hash Tries on GitHub
- ^ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011.
