Movatterモバイル変換

[0]ホーム

Jump to content

Hash tree (persistent data structure)

Add links

From Wikipedia, the free encyclopedia

Formatted data in computer science

This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources.
Find sources: "Hash tree" persistent data structure – news ·newspapers ·books ·scholar ·JSTOR(April 2024)

In computer science, ahash tree (orhashtrie) is apersistent data structure that can be used to implementsets andmaps, intended to replacehash tables inpurely functional programming. In its basic form, a hash tree stores thehashes 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 andCtries are refined versions of this data structure, using particular type of trie implementations.^[1]

References

[edit]

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

v t e Tree data structures
Search trees (dynamic sets, associative arrays)	2–3 2–3–4 AA (a,b) AVL B K-Dimensional B+ B* B^x Binary search Optimal Self-balancing Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicitk-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Rope Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Thiscomputer-programming-related article is astub. You can help Wikipedia byexpanding it.

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

Categories:

Hidden categories:

[8]ページ先頭