• Images
• Videos
• Documents
• Books
• Articles

Operation

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

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³ with negligible impact on performance.

Implementation details

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.

Implementations

The programming languages Clojure,⁴ Scala, and Frege⁵ 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.⁶ Another Haskell library "stm-containers" adapts the algorithm for use in the context of software transactional memory.⁷ A Javascript HAMT library ⁸ based on the Clojure implementation is also available. The Rubinius⁹ implementation of Ruby includes a HAMT, mostly written in Ruby but with 3¹⁰ primitives. Large maps in Erlang use a persistent HAMT representation internally since release 18.0.¹¹ The Pony programming language uses a HAMT for the hash map in its persistent collections package.¹² 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. ¹³

The concurrent lock-free version¹⁴ of the hash trie called Ctrie is a mutable thread-safe implementation which ensures progress. The data-structure has been proven to be correct¹⁵ - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties.

See also

• Judy array
• Radix tree

References

1. Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne. /wiki/Phil_Bagwell ↩

2. Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne. /wiki/Phil_Bagwell ↩

3. Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne. /wiki/Phil_Bagwell ↩

4. "clojure/clojure". GitHub. 8 December 2022. https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java ↩

5. "Frege/frege". GitHub. 7 December 2022. https://github.com/Frege/frege/blob/master/frege/data/HashMap.fr ↩

6. Johan Tibell, A. Announcing unordered-containers 0.2 http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html ↩

7. Nikita Volkov, Announcing the "stm-containers" library, 2014 https://nikita-volkov.github.io/stm-containers/ ↩

8. "mattbierner/hamt". GitHub. 27 November 2022. https://github.com/mattbierner/hamt ↩

9. "Ruby source file of Rubinius's HAMT". GitHub. https://github.com/rubinius/rubinius/blob/540a4b446991e4d5c956023d37ec4f95372d539d/kernel/common/hash_hamt.rb ↩

10. https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 [dead link] https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 ↩

11. "Erlang Programming Language". http://www.erlang.org/news/86 ↩

12. "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26. https://github.com/ponylang/ponyc/blob/master/packages/collections/persistent/map.pony ↩

13. "API docs for Rust im-rc crate". https://docs.rs/im/ ↩

14. Prokopec, A. Implementation of Concurrent Hash Tries on GitHub https://github.com/axel22/Ctries ↩

15. Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011. http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf ↩