Hash array mapped trie
 | This article may be too technical for most readers to understand. (October 2019) |
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 persistent 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 im and im-rc crates, which provide persistent collection types for the Rust programming language, use a HAMT for their persistent hash tables and hash sets. [11]
The concurrent lock-free version[12] of the hash trie called Ctrie is a mutable thread-safe implementation which ensures progress. The data-structure has been proven to be correct[13] - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties.
See also
[edit]References
[edit]- ^ a b c Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
- ^ "clojure/clojure". GitHub. 8 December 2022.
- ^ "Frege/frege". GitHub. 7 December 2022.
- ^ Johan Tibell, A. Announcing unordered-containers 0.2
- ^ Nikita Volkov, Announcing the "stm-containers" library, 2014
- ^ "mattbierner/hamt". GitHub. 27 November 2022.
- ^ "Ruby source file of Rubinius's HAMT". GitHub.
- ^ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 [dead link]
- ^ "Erlang Programming Language".
- ^ "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26.
- ^ "API docs for Rust im-rc crate".
- ^ Prokopec, A. Implementation of Concurrent Hash Tries on GitHub
- ^ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011.