Class FrequencySketch<E>
- java.lang.Object
-
- com.github.benmanes.caffeine.cache.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, requiringensureCapacity(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 thatensureCapacity(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.
-
-
-
Field Detail
-
SEED
static final long[] SEED
-
RESET_MASK
static final long RESET_MASK
- See Also:
- Constant Field Values
-
ONE_MASK
static final long ONE_MASK
- See Also:
- Constant Field Values
-
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, requiringensureCapacity(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 thatensureCapacity(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 hashi
- 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)
-
-