1 unstable release

0.1.0 Nov 8, 2020

#1227 in Data structures

MIT/Apache

58KB
1.5K SLoC

HAMST - Hash Array Mapped Shareable Trie

An HAMT data structure in rust, that uses immutable nodes that are shareable between new copies.

Modification in this HAMT, only create new nodes and leave the previous nodes available for any remaining old copies. Once the root of a copy disappear, then all the nodes that are unique to this copy, are garbage collected also.


lib.rs:

HAMST - Hash Array Mapped Shareable Tries

Each key is hashed and store related to the hash value.

When cloning the data structure, the nodes are shared, so that the operation is is really cheap. When modifying the data structure, after an explicit thawing, the mutable structure share the unmodified node and only nodes requiring modification will be re-created from the node onwards to the leaf.

No runtime deps