Package io.grpc

Class PersistentHashArrayMappedTrie

java.lang.Object
io.grpc.PersistentHashArrayMappedTrie

final class PersistentHashArrayMappedTrie extends 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.