Class FrequencySketch<E>


  • @NotThreadSafe
    final class FrequencySketch<E>
    extends java.lang.Object
    A probabilistic multiset for estimating the popularity of an element within a time window. The maximum frequency of an element is limited to 15 (4-bits) and an aging process periodically halves the popularity of all elements.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static long ONE_MASK  
      (package private) int randomSeed  
      (package private) static long RESET_MASK  
      (package private) int sampleSize  
      (package private) static long[] SEED  
      (package private) int size  
      (package private) long[] table  
      (package private) int tableMask  
    • Constructor Summary

      Constructors 
      Constructor Description
      FrequencySketch()
      Creates a lazily initialized frequency sketch, requiring ensureCapacity(long) be called when the maximum size of the cache has been determined.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static int ceilingNextPowerOfTwo​(int x)  
      void ensureCapacity​(long maximumSize)
      Initializes and increases the capacity of this FrequencySketch instance, if necessary, to ensure that it can accurately estimate the popularity of elements given the maximum size of the cache.
      int frequency​(E e)
      Returns the estimated number of occurrences of an element, up to the maximum (15).
      void increment​(E e)
      Increments the popularity of the element if it does not exceed the maximum (15).
      (package private) boolean incrementAt​(int i, int j)
      Increments the specified counter by 1 if it is not already at the maximum value (15).
      (package private) int indexOf​(int item, int i)
      Returns the table index for the counter at the specified depth.
      boolean isNotInitialized()
      Returns if the sketch has not yet been initialized, requiring that ensureCapacity(long) is called before it begins to track frequencies.
      (package private) void reset()
      Reduces every counter by half of its original value.
      (package private) int spread​(int x)
      Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • SEED

        static final long[] SEED
      • randomSeed

        final int randomSeed
      • sampleSize

        int sampleSize
      • tableMask

        int tableMask
      • table

        long[] table
      • size

        int size
    • Constructor Detail

      • FrequencySketch

        public FrequencySketch()
        Creates a lazily initialized frequency sketch, requiring ensureCapacity(long) be called when the maximum size of the cache has been determined.
    • Method Detail

      • ensureCapacity

        public void ensureCapacity​(@Nonnegative
                                   long maximumSize)
        Initializes and increases the capacity of this FrequencySketch instance, if necessary, to ensure that it can accurately estimate the popularity of elements given the maximum size of the cache. This operation forgets all previous counts when resizing.
        Parameters:
        maximumSize - the maximum size of the cache
      • isNotInitialized

        public boolean isNotInitialized()
        Returns if the sketch has not yet been initialized, requiring that ensureCapacity(long) is called before it begins to track frequencies.
      • frequency

        @Nonnegative
        public int frequency​(@Nonnull
                             E e)
        Returns the estimated number of occurrences of an element, up to the maximum (15).
        Parameters:
        e - the element to count occurrences of
        Returns:
        the estimated number of occurrences of the element; possibly zero but never negative
      • increment

        public void increment​(@Nonnull
                              E e)
        Increments the popularity of the element if it does not exceed the maximum (15). The popularity of all elements will be periodically down sampled when the observed events exceeds a threshold. This process provides a frequency aging to allow expired long term entries to fade away.
        Parameters:
        e - the element to add
      • incrementAt

        boolean incrementAt​(int i,
                            int j)
        Increments the specified counter by 1 if it is not already at the maximum value (15).
        Parameters:
        i - the table index (16 counters)
        j - the counter to increment
        Returns:
        if incremented
      • reset

        void reset()
        Reduces every counter by half of its original value.
      • indexOf

        int indexOf​(int item,
                    int i)
        Returns the table index for the counter at the specified depth.
        Parameters:
        item - the element's hash
        i - the counter depth
        Returns:
        the table index
      • spread

        int spread​(int x)
        Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.
      • ceilingNextPowerOfTwo

        static int ceilingNextPowerOfTwo​(int x)