Editing Persistent data structure (section)

=== Persistent hash array mapped trie ===
A persistent hash array mapped trie is a specialized variant of a [[hash array mapped trie]] that will preserve previous versions of itself on any updates. It is often used to implement a general purpose persistent map data structure.<ref name=":1">{{Citation|last=BoostCon|title=C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++"|date=2017-06-13|url=https://www.youtube.com/watch?v=WT9kmIE3Uis |archive-url=https://ghostarchive.org/varchive/youtube/20211221/WT9kmIE3Uis |archive-date=2021-12-21 |url-status=live|access-date=2018-10-22}}{{cbignore}}</ref>

Hash array mapped tries were originally described in a 2001 paper by [[Phil Bagwell]] entitled "Ideal Hash Trees". This paper presented a mutable [[Hash table]] where "Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches".<ref>{{Cite journal|last=Phil|first=Bagwell|date=2001|title=Ideal Hash Trees|url=https://infoscience.epfl.ch/record/64398|language=en}}</ref> This data structure was then modified by [[Rich Hickey]] to be fully persistent for use in the [[Clojure]] programming language.<ref>{{Cite web|url=https://www.infoq.com/presentations/Are-We-There-Yet-Rich-Hickey|title=Are We There Yet?|website=InfoQ|access-date=2018-10-22}}</ref>

Conceptually, hash array mapped tries work similar to any generic [[Tree (data structure)|tree]] in that they store nodes hierarchically and retrieve them by following a path down to a particular element. The key difference is that Hash Array Mapped Tries first use a [[hash function]] to transform their lookup key into a (usually 32 or 64 bit) integer. The path down the tree is then determined by using slices of the binary representation of that integer to index into a [[Sparse matrix|sparse array]] at each level of the tree. The leaf nodes of the tree behave similar to the buckets used to construct [[hash table]]s and may or may not contain multiple candidates depending on [[hash collision]]s.<ref name=":1" />

Most implementations of persistent hash array mapped tries use a branching factor of 32 in their implementation. This means that in practice while insertions, deletions, and lookups into a persistent hash array mapped trie have a computational complexity of ''O''(log ''n''), for most applications they are effectively constant time, as it would require an extremely large number of entries to make any operation take more than a dozen steps.<ref>{{Cite journal |last1=Steindorfer |first1=Michael J. |last2=Vinju |first2=Jurgen J. |date=2015-10-23 |title=Optimizing hash-array mapped tries for fast and lean immutable JVM collections |journal=ACM SIGPLAN Notices |volume=50 |issue=10 |pages=783–800 |doi=10.1145/2814270.2814312 |s2cid=10317844 |issn=0362-1340|url=https://ir.cwi.nl/pub/24029 }}</ref>