In computer science, a hash tree (or hash
trie
In computer science, a trie, also called digital tree or prefix tree, is a type of ''k''-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes def ...
) is a
persistent data structure
In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (v ...
that can be used to implement
sets and
maps
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
, intended to replace
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
s in
purely functional programming
In computer science, purely functional programming usually designates a programming paradigm—a style of building the structure and elements of computer programs—that treats all computation as the evaluation of function (mathematics), mathemati ...
. In its basic form, a hash tree stores the
hashes of its keys, regarded as strings of bits, in a trie, with the actual keys and (optional) values stored at the trie's "final" nodes.
Hash array mapped trie
A hash array mapped trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.
It is a refined version of the more general notion of a Hash tree (persistent data structure), ...
s and
Ctrie
A concurrent hash-trie or CtrieProkopec, A. et al. (2011Cache-Aware Lock-Free Concurrent Hash Tries Technical Report, 2011.Prokopec, A., Bronson N., Bagwell P., Odersky M. (2012Concurrent Tries with Efficient Non-Blocking Snapshots/ref> is a concu ...
s are refined versions of this data structure, using particular type of trie implementations.
References
Functional data structures
Hashing
{{compu-prog-stub