Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hash tree (persistent data structure)
open-in-new
<p>In computer science, a hash tree (or hash <a href="/facts/Trie/cXNr0ScT">trie</a>) is a <a href="/facts/Persistent_data_structure/K7IpHlkR">persistent data structure</a> that can be used to implement <a href="/facts/Set_(abstract_data_type)/ovoXUmF9">sets</a> and <a href="/facts/Associative_array/IFGd2xcP">maps</a>, intended to replace <a href="/facts/Hash_table/Ht4ptDPF">hash tables</a> in <a href="/facts/Purely_functional_programming/am3DcNAd">purely functional programming</a>. In its basic form, a hash tree stores the <a href="/facts/Hash_function/rk6MlCt3">hashes</a> 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. </p><p><a href="/facts/Hash_array_mapped_trie/5IBsQBhU">Hash array mapped tries</a> and <a href="/facts/Ctrie/GD1trrAb">Ctries</a> are refined versions of this data structure, using particular type of trie implementations. </p>