Package org.apache.flink.table.runtime.util.collections

Class OptimizableHashSet

  • Direct Known Subclasses:
    DoubleHashSet, FloatHashSet, IntHashSet, LongHashSet, ObjectHashSet, ShortHashSet
    public abstract class OptimizableHashSet
extends Object
    A type-specific hash set with with a fast, small-footprint implementation. Refer to the implementation of fastutil.

    Instances of this class use a hash table to represent a set. The table is enlarged as needed by doubling its size when new entries are created.

    The difference with fastutil is that if the range of the maximum and minimum values is small or the data is dense, a Dense array will be used to greatly improve the access speed.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected boolean containsNull
      Is this set has a null key.
      protected boolean containsZero
      Is this set has a zero key.
      static int DEFAULT_INITIAL_SIZE
      The initial default size of a hash table.
      static float DEFAULT_LOAD_FACTOR
      The default load factor of a hash table.
      static int DENSE_THRESHOLD
      Decide whether to convert to dense mode if it does not require more memory or could fit within L1 cache.
      protected float f
      The acceptable load factor.
      protected boolean isDense
      Is now dense mode.
      protected int mask
      The mask for wrapping a position counter.
      protected int maxFill
      Threshold after which we rehash.
      protected int n
      The current table size.
      protected int size
      Number of entries in the set.
      protected boolean[] used
      Used array for dense mode.

    • Constructor Summary

      Constructors 
      Constructor Description
      OptimizableHashSet​(int expected, float f)  

    • Field Detail

      • DEFAULT_INITIAL_SIZE

        public static final int DEFAULT_INITIAL_SIZE
        The initial default size of a hash table.
        See Also:
        Constant Field Values

      • DEFAULT_LOAD_FACTOR

        public static final float DEFAULT_LOAD_FACTOR
        The default load factor of a hash table.
        See Also:
        Constant Field Values

      • DENSE_THRESHOLD

        public static final int DENSE_THRESHOLD
        Decide whether to convert to dense mode if it does not require more memory or could fit within L1 cache.
        See Also:
        Constant Field Values

      • f

        protected final float f
        The acceptable load factor.

      • mask

        protected int mask
        The mask for wrapping a position counter.

      • n

        protected int n
        The current table size.

      • maxFill

        protected int maxFill
        Threshold after which we rehash. It must be the table size times f.

      • containsNull

        protected boolean containsNull
        Is this set has a null key.

      • containsZero

        protected boolean containsZero
        Is this set has a zero key.

      • size

        protected int size
        Number of entries in the set.

      • isDense

        protected boolean isDense
        Is now dense mode.

      • used

        protected boolean[] used
        Used array for dense mode.

    • Constructor Detail

      • OptimizableHashSet

        public OptimizableHashSet​(int expected,
                          float f)

    • Method Detail

      • addNull

        public void addNull()
        Add a null key.

      • containsNull

        public boolean containsNull()
        Is there a null key.

      • realSize

        protected int realSize()

      • optimize

        public abstract void optimize()
        Decide whether to convert to dense mode.

      • nextPowerOfTwo

        public static long nextPowerOfTwo​(long x)
        Return the least power of two greater than or equal to the specified value.

        Note that this function will return 1 when the argument is 0.

        Parameters:
        x - a long integer smaller than or equal to 262.
        Returns:
        the least power of two greater than or equal to the specified value.

      • maxFill

        public static int maxFill​(int n,
                          float f)
        Returns the maximum number of entries that can be filled before rehashing.
        Parameters:
        n - the size of the backing array.
        f - the load factor.
        Returns:
        the maximum number of entries before rehashing.

      • arraySize

        public static int arraySize​(int expected,
                            float f)
        Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil( expected / f ).
        Parameters:
        expected - the expected number of elements in a hash table.
        f - the load factor.
        Returns:
        the minimum possible size for a backing array.
        Throws:
        IllegalArgumentException - if the necessary size is larger than 230.