Package io.grpc
Class PersistentHashArrayMappedTrie
- java.lang.Object
-
- io.grpc.PersistentHashArrayMappedTrie
-
final class PersistentHashArrayMappedTrie extends java.lang.Object
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 Classes Modifier and Type Class Description (package private) static class
PersistentHashArrayMappedTrie.CollisionLeaf<K,V>
(package private) static class
PersistentHashArrayMappedTrie.CompressedIndex<K,V>
(package private) static class
PersistentHashArrayMappedTrie.Leaf<K,V>
(package private) static interface
PersistentHashArrayMappedTrie.Node<K,V>
-
Constructor Summary
Constructors Modifier Constructor Description private
PersistentHashArrayMappedTrie()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (package private) static <K,V>
Vget(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.
-
-
-
Method Detail
-
get
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.
-
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.
-
-