Class FrequencySketch<E>

java.lang.Object
com.github.benmanes.caffeine.cache.FrequencySketch<E>

final class FrequencySketch<E> extends 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 final long
     
    (package private) static final long
     
    (package private) int
     
    (package private) static final long[]
     
    (package private) int
     
    (package private) long[]
     
    (package private) int
     
  • Constructor Summary

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

    Modifier and Type
    Method
    Description
    void
    ensureCapacity(@org.checkerframework.checker.index.qual.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.
    @org.checkerframework.checker.index.qual.NonNegative int
    frequency(@NonNull E e)
    Returns the estimated number of occurrences of an element, up to the maximum (15).
    void
    increment(@NonNull 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
    Returns if the sketch has not yet been initialized, requiring that ensureCapacity(long) is called before it begins to track frequencies.
    (package private) void
    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 Details

    • SEED

      static final long[] SEED
    • RESET_MASK

      static final long RESET_MASK
      See Also:
    • ONE_MASK

      static final long ONE_MASK
      See Also:
    • sampleSize

      int sampleSize
    • tableMask

      int tableMask
    • table

      long[] table
    • size

      int size
  • Constructor Details

    • 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 Details

    • ensureCapacity

      public void ensureCapacity(@org.checkerframework.checker.index.qual.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

      public @org.checkerframework.checker.index.qual.NonNegative 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.