Hash_tree_persistent_data_structure

🌐 🇮🇩 ID 🇺🇸 EN 🇩🇪 DE 🇫🇷 FR 🇪🇸 ES 🇷🇺 RU 🇮🇹 IT 🇵🇱 PL 🇨🇳 ZH 🇯🇵 JA 🇧🇷 PT ↗ Wikipedia

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Hash tree" persistent data structure – news · newspapers · books · scholar · JSTOR (April 2024)

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

edit

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

This computer-programming-related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Persistent data structure

In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when

Hash tree

up hash tree in Wiktionary, the free dictionary. In computer science, hash tree may refer to: Hashed array tree Hash tree (persistent data structure),

Data structure

Relational databases commonly use B-tree indice for data retrieval, while compiler implementations usually use hash tables to look up identifiers. Filesystems

Associative array

efficient data structures that implement associative arrays. The two major solutions to the dictionary problem are hash tables and search trees. It is sometimes

Purely functional data structure

Such a data structure is necessarily persistent. However, not all persistent data structures are purely functional. For example, a persistent array is

Hash trie

In computer science, hash trie can refer to: Hash tree (persistent data structure), a trie used to map hash values to keys A space-efficient implementation

Hash array mapped trie

version of the more general notion of a hash tree. A HAMT is an array mapped trie where the keys are first hashed to ensure an even distribution of keys