# hamt-sync
[![Circle CI](https://img.shields.io/circleci/project/github/raviqqe/hamt-sync.svg?style=flat-square)](https://circleci.com/gh/raviqqe/hamt-sync)
[![Crates.io](https://img.shields.io/crates/v/hamt-sync.svg?style=flat-square)](https://crates.io/crates/hamt-sync)
[![License](https://img.shields.io/github/license/raviqqe/hamt-sync.svg?style=flat-square)](https://opensource.org/licenses/MIT)
HAMT implementation whose sub-trees can be shared over threads.
[Hash-Array Mapped Trie (HAMT)](https://en.wikipedia.org/wiki/Hash_array_mapped_trie)
is a data structure popular as a map (a.k.a. associative array or dictionary)
or set.
Its immutable variant is adopted widely by functional programming languages
like Scala and Clojure to implement immutable and memory-efficient associative
arrays and sets.
## Technical notes
The implementation canonicalizes tree structures of HAMTs by eliminating
intermediate nodes during delete operations as described
in [the CHAMP paper][champ].
## References
- [Ideal Hash Trees](https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf)
- [Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections][champ]
## License
[MIT](LICENSE)
[champ]: https://michael.steindorfer.name/publications/oopsla15.pdf