Package io.grpc
Class PersistentHashArrayMappedTrie
java.lang.Object
io.grpc.PersistentHashArrayMappedTrie
A persistent (copy-on-write) hash tree/trie. Collisions are handled
linearly. Delete is not supported, but replacement is. The implementation
favors simplicity and low memory allocation during insertion. Although the
asymptotics are good, it is optimized for small sizes like less than 20;
"unbelievably large" would be 100.
Inspired by popcnt-based compression seen in Ideal Hash Trees, Phil Bagwell (2000). The rest of the implementation is ignorant of/ignores the paper.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static final class
(package private) static final class
(package private) static final class
(package private) static interface
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static <K,
V> V get
(PersistentHashArrayMappedTrie.Node<K, V> root, K key) Returns the value with the specified key, ornull
if it does not exist.(package private) static <K,
V> PersistentHashArrayMappedTrie.Node <K, V> put
(PersistentHashArrayMappedTrie.Node<K, V> root, K key, V value) Returns a new trie where the key is set to the specified value.
-
Constructor Details
-
PersistentHashArrayMappedTrie
private PersistentHashArrayMappedTrie()
-
-
Method Details
-
get
Returns the value with the specified key, ornull
if it does not exist. -
put
static <K,V> PersistentHashArrayMappedTrie.Node<K,V> put(PersistentHashArrayMappedTrie.Node<K, V> root, K key, V value) Returns a new trie where the key is set to the specified value.
-