Jump to content

Hash tree (persistent data structure)

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Qwertyus (talk | contribs) at 11:18, 15 May 2013 (actually, HAMTs could be described here as well; the basic properties listed in their article are due to them being hash trees). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a hash tree 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 are a refined version of this data structure, using a particular type of trie implementation.[1]

References

  1. ^ a b Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
Stub icon

This computer-programming-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_tree_(persistent_data_structure)&oldid=555199063"