Hash tree (persistent data structure): Difference between revisions

Revision as of 10:06, 18 April 2014

Revision as of 23:03, 10 March 2015

Line 1:

{{mergeto|Merkle tree|discuss=Talk:Merkle_tree#Merger_Proposal_Hash_tree_.28persistent_data_structure.29|date=March 2015}}

In computer science, a '''hash tree''' (or '''hash [[trie]]''') is a [[persistent data structure]] that can be used to implement [[Set (abstract data type)|sets]] and [[Associative array|maps]], intended to replace [[hash table]]s in [[purely functional]] programming. In its basic form, a hash tree stores the [[Hash function|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.<ref name="bagwell">{{cite report

|title=Ideal Hash Trees