Class BitHashSet

  • All Implemented Interfaces:
    java.lang.Iterable<java.lang.Integer>

    public class BitHashSet
    extends java.lang.Object
    implements java.lang.Iterable<java.lang.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 Summary

      Constructors 
      Constructor Description
      BitHashSet()  
      BitHashSet​(int cacheSize)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(java.lang.Integer elementBit)  
      int cachedSize()  
      boolean contains​(java.lang.Integer elementBit)  
      boolean isEmpty()  
      java.util.Iterator<java.lang.Integer> iterator()
      This function is not thread-safe, need to synchronized when iterate through this set.
      boolean remove​(java.lang.Integer elementBit)  
      int remove​(java.util.Set<java.lang.Integer> bitSet, java.util.BitSet bits)
      Remove the watches, and return the number of watches being removed.
      int size()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator
    • Constructor Detail

      • BitHashSet

        public BitHashSet()
      • BitHashSet

        public BitHashSet​(int cacheSize)
    • Method Detail

      • add

        public boolean add​(java.lang.Integer elementBit)
      • remove

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

        public boolean remove​(java.lang.Integer elementBit)
      • contains

        public boolean contains​(java.lang.Integer elementBit)
      • size

        public int size()
      • iterator

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

        public int cachedSize()
      • isEmpty

        public boolean isEmpty()