Hash tree (persistent data structure)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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.[1]

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

References

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


Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_tree_(persistent_data_structure)&oldid=732879549"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Hash_tree_(persistent_data_structure)
This page is based on the copyrighted Wikipedia article "Hash tree (persistent data structure)"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA