Package io.grpc

Class 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.