Class BitHashSet

java.lang.Object
org.apache.zookeeper.server.util.BitHashSet
All Implemented Interfaces:
Iterable<Integer>
public class BitHashSet extends Object implements Iterable<Integer>
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

      public boolean add(Integer elementBit)

    • remove

      public int remove(Set<Integer> bitSet, BitSet bits)
      Remove the watches, and return the number of watches being removed.

    • remove

      public boolean remove(Integer elementBit)

    • contains

      public boolean contains(Integer elementBit)

    • size

      public int size()

    • iterator

      public Iterator<Integer> iterator()
      This function is not thread-safe, need to synchronized when iterate through this set.
      Specified by:
      iterator in interface Iterable<Integer>

    • cachedSize

      public int cachedSize()

    • isEmpty

      public boolean isEmpty()