Expand description
Persistent hash maps and sets: hash tries whose nodes are shared between versions. A clone is O(1); an update copies the path from the root to the key and shares everything else, and a map no other version shares is updated in place.
Inner nodes branch on 5 hash bits per level, high bits first; a
subtree of at most LEAF pairs is a flat leaf sorted by hash. A
key set has one tree shape for a given hasher, and iteration follows
it, in hash order, so with a deterministic hasher (the default) the
order is the same in every process. Map::root and
NodeHandle expose the tree to a codec that must reproduce its
sharing.
Structs§
- FxBuild
Hasher - An implementation of
BuildHasherthat producesFxHashers. - Iter
- A walk of a tree in hash order, with a frame per inner level.
- Map
- A persistent hash map.
- Node
Handle - An owned node, built by
innerorleaf, or kept from aNodeRef. A map is assembled from handles withMap::from_root. - NodeRef
- A borrowed node of a map’s tree, for a codec that must reproduce
the tree’s sharing. Two views with the same
identityare the same node; aNodeHandlefromkeeppins that identity for as long as it is held. - Pairs
- Set
- A persistent hash set.
- SetIter
- Slots
Enums§
- Contents
- What a node holds.
- NewSlot
- A slot of an inner node to create.
- SlotRef
- A slot of an inner node: a lone pair, or a subtree.
Constants§
- LEAF
- The most pairs a leaf holds, unless all of them share one hash.