imported>AnomieBOT: Dating maintenance tags: {{Citation needed}}

2025-06-20T16:20:36Z

Dating maintenance tags: {{Citation needed}}

New page

{{Short description|Formatted data in computer science}}
{{Technical|date=October 2019}}
A '''hash array mapped trie'''<ref name="bagwell" /> ('''HAMT''', {{IPAc-en|ˈ|h|æ|m|t|}}) is an implementation of an [[associative array]] that combines the characteristics of a [[hash table]] and an [[array mapped trie]].<ref name="bagwell">{{cite report
|title=Ideal Hash Trees
|author=Phil Bagwell
|author-link=Phil Bagwell
|publisher=Infoscience Department, [[École Polytechnique Fédérale de Lausanne]]
|url=http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf
|year=2000
}}</ref>
It is a refined version of the more general notion of a [[Hash tree (persistent data structure)|hash tree]].

== 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.{{citation needed|date=June 2025}} 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<ref name="bagwell" /> with negligible impact on performance.

== Implementation details ==
Implementation of a HAMT involves the use of the [[Hamming weight|population count]] function, which counts the number of ones in the binary representation of a number. This operation is available in [[Hamming weight#Processor support|many instruction set architectures]], but it is [[Hamming weight#Language support|available in only some high-level languages]]. Although population count can be implemented in software in [[Big-O notation|O(1)]] time using a [[Hamming weight#Efficient implementation|series of shift and add instructions]], doing so may perform the operation an order of magnitude slower.{{citation needed|date=October 2016}}

== Implementations ==
The programming languages [[Clojure]],<ref>{{cite web|url=https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java|title=clojure/clojure|website=GitHub|date=8 December 2022 }}</ref> [[Scala (programming language)|Scala]], and [[Frege (programming language)|Frege]]<ref>{{cite web|url=https://github.com/Frege/frege/blob/master/frege/data/HashMap.fr|title=Frege/frege|website=GitHub|date=7 December 2022 }}</ref> use a [[Persistent data structure|persistent]] variant of hash array mapped tries for their native hash map type. The [[Haskell (programming language)|Haskell]] library "unordered-containers" uses the same to implement persistent map and set data structures.<ref>Johan Tibell, A. [http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html Announcing unordered-containers 0.2]</ref> Another Haskell library "stm-containers" adapts the algorithm for use in the context of [[software transactional memory]].<ref>Nikita Volkov, [https://nikita-volkov.github.io/stm-containers/ Announcing the "stm-containers" library], 2014</ref> A [[JavaScript|Javascript]] HAMT library <ref>{{cite web|url=https://github.com/mattbierner/hamt|title=mattbierner/hamt|website=GitHub|date=27 November 2022 }}</ref> based on the Clojure implementation is also available. The [[Rubinius]]<ref>{{cite web|url=https://github.com/rubinius/rubinius/blob/540a4b446991e4d5c956023d37ec4f95372d539d/kernel/common/hash_hamt.rb|title=Ruby source file of Rubinius's HAMT|website=[[GitHub]]|publisher=}}</ref> implementation of [[Ruby (programming language)|Ruby]] includes a HAMT, mostly written in Ruby but with 3<ref>https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 {{Dead link|date=February 2022}}</ref> primitives. Large maps in [[Erlang (programming language)|Erlang]] use a [[Persistent data structure|persistent]] HAMT representation internally since release 18.0.<ref>{{Cite web | url=http://www.erlang.org/news/86 | title=Erlang Programming Language}}</ref> The Pony programming language uses a HAMT for the hash map in its persistent collections package.<ref>{{Cite web | url=https://github.com/ponylang/ponyc/blob/master/packages/collections/persistent/map.pony | title=horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc| website=[[GitHub]]| date=2018-11-26}}</ref>
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.
<ref>{{cite web|url=https://docs.rs/im/|title=API docs for Rust im-rc crate}}</ref>

The concurrent lock-free version<ref>Prokopec, A. [https://github.com/axel22/Ctries Implementation of Concurrent Hash Tries on GitHub]</ref> of the hash trie called [[Ctrie]] is a mutable thread-safe implementation which ensures progress. The data-structure has been proven to be correct<ref>Prokopec, A. et al. (2011) [http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf Cache-Aware Lock-Free Concurrent Hash Tries]. Technical Report, 2011.</ref> - Ctrie operations have been shown to have the [[Atomicity (programming)|atomicity]], [[linearizability]] and [[lock free|lock-freedom]] properties.

== See also ==
* [[Judy array]]
* [[Radix tree]]

== References ==
{{Reflist}}

{{DEFAULTSORT:Hash Array Mapped Trie}}
[[Category:Associative arrays]]
[[Category:Hashing]]

Hash array mapped trie - Revision history

imported>AnomieBOT: Dating maintenance tags: {{Citation needed}}