Package org.apache.zookeeper.server.util
Class BitHashSet
java.lang.Object
org.apache.zookeeper.server.util.BitHashSet
Using BitSet to store all the elements, and use HashSet to cache limited
number of elements to find a balance between memory and time complexity.
Without HashSet, we need to use O(N) time to get the elements, N is
the bit numbers in elementBits. But we need to keep the size small to make
sure it doesn't cost too much in memory, there is a trade off between
memory and time complexity.
Previously, was deciding to dynamically switch between SparseBitSet and
HashSet based on the memory consumption, but it will take time to copy
data over and may have some herd effect of keep copying data from one
data structure to anther. The current solution can do a very good job
given most of the paths have limited number of elements.
-
Constructor Details
-
BitHashSet
public BitHashSet() -
BitHashSet
public BitHashSet(int cacheSize)
-
-
Method Details
-
add
-
remove
Remove the watches, and return the number of watches being removed. -
remove
-
contains
-
size
public int size() -
iterator
This function is not thread-safe, need to synchronized when iterate through this set. -
cachedSize
public int cachedSize() -
isEmpty
public boolean isEmpty()
-