Hash tree (persistent data structure): Difference between revisions

Revision as of 11:18, 15 May 2013

Latest revision as of 22:49, 23 December 2024

(12 intermediate revisions by 6 users not shown)

Line 1:

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

{{mergefrom|Hash array mapped trie}}

{{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 [[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

|author=Phil Bagwell

Line 8 ⟶ 9:

}}</ref>

[[Hash array mapped trie]]s areand a[[Ctrie]]s are refined versionversions of this data structure, using a particular type of trie implementationimplementations.<ref name="bagwell"/>

==References==

Line 17 ⟶ 18:

[[Category:Functional data structures]]

[[Category:Hashing]]

{{compu-prog-stub}}