Hash tree (persistent data structure)
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, a hash tree (or hash trie) is a persistent data structure that can be used to implement sets and maps, intended to replace hash tables in purely functional programming. 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.[1]
Hash array mapped tries and Ctries are refined versions of this data structure, using particular type of trie implementations.[1]
References
edit edit source- ^ a b Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
(dynamic sets,
associative arrays)
partitioning trees
Text derived from https://en.wikipedia.org/w/index.php?oldid=1264859772 under CC BY-SA 4.0; modifications have been made.