Crate champ_trie 

Persistent hash map based on CHAMP.

CHAMP (Compressed Hash-Array Mapped Prefix-tree) is a refined HAMT that guarantees canonical form: the same set of key-value pairs always produces the same trie structure, regardless of insertion order.

Key properties

• Canonical form: same contents = same structure
• O(1) structural equality: via incrementally maintained AdHash
• COW structural sharing: cheap copy, mutate-on-write
• Zero unsafe: enforced by #![forbid(unsafe_code)]

References

• Steindorfer & Vinju, 2015 — “Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections”, OOPSLA 2015
• Bagwell, 2001 — “Ideal Hash Trees”

Modules

adhash

AdHash — incremental structural hashing.

iter

Iterator types for CHAMP maps.

node

CHAMP trie node types and bitmap helpers.

store

Storage abstraction for CHAMP trie operations.

Structs

ChampCheckpoint

Saved map state for rollback.

ChampMap

Persistent hash map based on a CHAMP trie, single-threaded.

ChampMapSync

Persistent hash map based on a CHAMP trie, multi-threaded.