Hash tree (persistent data structure)

{{Short description|Formatted data in computer science}}

{{one source |date=April 2024}}

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.{{cite report

|title=Ideal Hash Trees

|author=Phil Bagwell

|publisher=Infoscience Department, École Polytechnique Fédérale de Lausanne

|url=http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf

|year=2000

}}

Hash array mapped tries and Ctries are refined versions of this data structure, using particular type of trie implementations.