public final class SieveCache<K extends Object, V extends Object>

SieveCache is an in-memory cache that holds strong references to a limited number of values determined by the cache's maxSize and the size of each value. When a value is added to a full cache, one or more existing values are evicted from the cache using the SIEVE algorithm. Complete details about the algorithm can be found in Zhang et al., 2024, SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches, NSDI'24 (paper).

Contrary to LruCache, SieveCache does not maintain a list of entries based on their access order, but on their insertion order. Eviction candidates are found by keeping track of the "visited" status of each entry. This means that reading a value using get prevents that entry from becoming an eviction candidate. In practice, SieveCache offers better hit ratio compared to LruCache.

The underlying implementation is also designed to avoid all allocations on insertion, removal, retrieval, and iteration. Allocations may still happen on insertion when the underlying storage needs to grow to accommodate newly added entries to the table. In addition, this implementation minimizes memory usage by avoiding the use of separate objects to hold key/value pairs. The implementation follows the implementation of ScatterMap.

By default, the size of the cache is measured in number of entries. The caller can choose the size and size unit of the values by passing their own sizeOf lambda, invoked whenever the cache needs to query the size of a value.

The createValueFromKey lambda can be used to compute values on demand from a key when querying for an entry that does not exist in the cache.

When a cached value is removed, either directly by the caller or via the eviction mechanism, you can use the onEntryRemoved lambda to execute any side effect or perform any necessary cleanup.

This implementation is not thread-safe: if multiple threads access this container concurrently, and one or more threads modify the structure of the map (insertion or removal for instance), the calling code must provide the appropriate synchronization. Multiple threads are safe to read from this map concurrently if no write is happening.

A SieveCache can hold a maximum of Int.MAX_VALUE - 1 entries, independent of their computed size.

Summary

Public constructors
<K extends Object, V extends Object> SieveCache(
    @IntRange(from = 1, to = 2147483646) int maxSize,
    @IntRange(from = 0, to = 2147483646) int initialCapacity,
    @NonNull Function2<@NonNull key, @NonNull value, @NonNull Integer> sizeOf,
    @NonNull Function1<@NonNull key, V> createValueFromKey,
    @NonNull Function4<@NonNull key, @NonNull oldValue, newValue, @NonNull Boolean, Unit> onEntryRemoved
)

Creates a new SieveCache.

Public methods
final boolean
all(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns true if all entries match the given predicate.
final boolean
any()

Returns true if this cache has at least one entry.
final boolean
any(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns true if at least one entry matches the given predicate.
final boolean
contains(@NonNull K key)

Returns true if the specified key is present in this cache, false otherwise.
final boolean

Returns true if the specified key is present in this cache, false otherwise.
final boolean

Returns true if the specified value is present in this hash map, false otherwise.
final int

Returns the number of entries in this cache.
final int
count(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns the number of entries matching the given predicate.
boolean
equals(Object other)

Compares the specified object other with this cache for equality.
final void

Removes all the entries from this cache.
final void
forEach(@NonNull Function2<@NonNull key, @NonNull value, Unit> block)

Iterates over every key/value pair stored in this cache by invoking the specified block lambda.
final void
forEachKey(@NonNull Function1<@NonNull key, Unit> block)

Iterates over every key stored in this cache by invoking the specified block lambda.
final void
forEachValue(@NonNull Function1<@NonNull value, Unit> block)

Iterates over every value stored in this cache by invoking the specified block lambda.
final V
get(@NonNull K key)

Returns the value for key if it exists in the cache or can be created by createValueFromKey.
final int

Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.
final int

Returns the number of elements held in the cache.
final int

Return the maximum size of the cache before adding new elements causes existing elements to be evicted.
final int

Size of the cache in the unit defined by the implementation of sizeOf (by default, the number of elements).
int

Returns the hash code value for this cache.
final boolean

Indicates whether this cache is empty.
final boolean

Returns true if this cache is not empty.
final void

Removes the specified key and its associated value from the map.
final void
minusAssign(@NonNull K[] keys)

Removes the specified keys and their associated value from the map.
final void

Removes the specified keys and their associated value from the map.
final void

Removes the specified keys and their associated value from the map.
final void

Removes the specified keys and their associated value from the map.
final void

Removes the specified keys and their associated value from the map.
final boolean

Returns true if this cache has no entries.
final void

Puts all the key/value mappings in the from map into this map.
final void

Puts all the key/value mappings in the from map into this map.
final void

Puts all the key/value mappings in the from map into this map.
final void

Puts the key/value mapping from the pair in this cache, using the first element as the key, and the second element as the value.
final void
plusAssign(@NonNull Pair[] pairs)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
final void

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
final void

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value.
final V
put(@NonNull K key, @NonNull V value)

Adds value to the cache using the specific key.
final void
putAll(@NonNull Map<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this cache.
final void

Puts all the key/value mappings in the from map into this cache.
final void

Puts all the key/value mappings in the from cache into this cache.
final void
putAll(@NonNull Pair[] pairs)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
final void

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
final void

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value.
final V
remove(@NonNull K key)

Removes the specified key and its associated value from the cache.
final boolean
remove(@NonNull K key, @NonNull V value)

Removes the specified key and its associated value from the cache if the associated value equals value.
final void
removeIf(
    @NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate
)

Removes any mapping for which the specified predicate returns true.
final void
resize(@IntRange(from = 1, to = 2147483646) int maxSize)

Sets the maximum size of the cache to maxSize, in the unit defined by the implementation of sizeOf.
final void
set(@NonNull K key, @NonNull V value)

Adds value to the cache using the specific key.
@NonNull String
final void
trimToSize(int maxSize)

Remove entries until the total size of the remaining entries is less than or equal to maxSize.

Public constructors

SieveCache

public <K extends Object, V extends Object> SieveCache(
    @IntRange(from = 1, to = 2147483646) int maxSize,
    @IntRange(from = 0, to = 2147483646) int initialCapacity,
    @NonNull Function2<@NonNull key, @NonNull value, @NonNull Integer> sizeOf,
    @NonNull Function1<@NonNull key, V> createValueFromKey,
    @NonNull Function4<@NonNull key, @NonNull oldValue, newValue, @NonNull Boolean, Unit> onEntryRemoved
)

Creates a new SieveCache.

Parameters
@IntRange(from = 1, to = 2147483646) int maxSize

For caches that do not override sizeOf, this is the maximum number of entries in the cache. For all other caches, this is the maximum sum of the sizes of the entries in this cache. The maximum size must be strictly greater than 0 and must be less than or equal to Int.MAX_VALUE - 1.
@IntRange(from = 0, to = 2147483646) int initialCapacity

The initial desired capacity for this cache. The cache will honor this value by guaranteeing its internal structures can hold that many entries without requiring any allocations. The initial capacity can be set to 0.
@NonNull Function2<@NonNull key, @NonNull value, @NonNull Integer> sizeOf

Returns the size of the entry for the specified key and value. The size of an entry cannot change after it was added to the cache, and must be >= 0.
@NonNull Function1<@NonNull key, V> createValueFromKey

Called after a cache miss to compute a value for the specified key. Returning null from this lambda indicates that no value can be computed.
@NonNull Function4<@NonNull key, @NonNull oldValue, newValue, @NonNull Boolean, Unit> onEntryRemoved

Called for entries that have been removed by the user of the cache, or automatically evicted. The lambda is supplied with multiple parameters. The key of the entry being removed or evicted. The original value (oldValue) of the entry if the entry is being evicted or replaced. The new value (newValue) for the key, if it exists. If non-null, the removal was caused by a put() or a set(), otherwise it was caused by an eviction or a removal. A boolean (evicted) set to true if the entry was evicted to make space in the cache, or set to false if the removal happened on demand or while replacing an existing value with put.

Public methods

all

Added in 1.5.0-alpha01
public final boolean all(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns true if all entries match the given predicate.

any

Added in 1.5.0-alpha01
public final boolean any()

Returns true if this cache has at least one entry.

any

Added in 1.5.0-alpha01
public final boolean any(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns true if at least one entry matches the given predicate.

contains

Added in 1.5.0-alpha01
public final boolean contains(@NonNull K key)

Returns true if the specified key is present in this cache, false otherwise.

containsKey

Added in 1.5.0-alpha01
public final boolean containsKey(@NonNull K key)

Returns true if the specified key is present in this cache, false otherwise.

containsValue

Added in 1.5.0-alpha01
public final boolean containsValue(@NonNull V value)

Returns true if the specified value is present in this hash map, false otherwise.

count

Added in 1.5.0-alpha01
public final int count()

Returns the number of entries in this cache.

count

Added in 1.5.0-alpha01
public final int count(@NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate)

Returns the number of entries matching the given predicate.

equals

public boolean equals(Object other)

Compares the specified object other with this cache for equality. The two objects are considered equal if other:

  • Is a SieveCache

  • Has the same size and count as this cache

  • Contains key/value pairs equal to this cache's pair

evictAll

Added in 1.5.0-alpha01
public final void evictAll()

Removes all the entries from this cache. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.

forEach

Added in 1.5.0-alpha01
public final void forEach(@NonNull Function2<@NonNull key, @NonNull value, Unit> block)

Iterates over every key/value pair stored in this cache by invoking the specified block lambda. The iteration order is not specified.

NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.

forEachKey

Added in 1.5.0-alpha01
public final void forEachKey(@NonNull Function1<@NonNull key, Unit> block)

Iterates over every key stored in this cache by invoking the specified block lambda.

NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.

forEachValue

Added in 1.5.0-alpha01
public final void forEachValue(@NonNull Function1<@NonNull value, Unit> block)

Iterates over every value stored in this cache by invoking the specified block lambda.

NOTE: Iterating over the content of the cache does not mark entries as recently visited, and therefore does not affect which entries get evicted first.

get

Added in 1.5.0-alpha01
public final V get(@NonNull K key)

Returns the value for key if it exists in the cache or can be created by createValueFromKey. Return null if a value is not present in the cache and cannot be created.

getCapacity

Added in 1.5.0-alpha01
public final int getCapacity()

Returns the number of entries that can be stored in this cache without requiring internal storage reallocation.

See also
count

getCount

Added in 1.5.0-alpha01
public final int getCount()

Returns the number of elements held in the cache.

See also
capacity

getMaxSize

Added in 1.5.0-alpha01
public final int getMaxSize()

Return the maximum size of the cache before adding new elements causes existing elements to be evicted. The unit of maxSize is defined by the implementation of sizeOf. Using the default implementation of sizeOf, maxSize indicates the a maximum number of elements.

See also
size

getSize

Added in 1.5.0-alpha01
public final int getSize()

Size of the cache in the unit defined by the implementation of sizeOf (by default, the number of elements).

See also
maxSize

hashCode

public int hashCode()

Returns the hash code value for this cache. The hash code the sum of the hash codes of each key/value pair.

isEmpty

Added in 1.5.0-alpha01
public final boolean isEmpty()

Indicates whether this cache is empty.

isNotEmpty

Added in 1.5.0-alpha01
public final boolean isNotEmpty()

Returns true if this cache is not empty.

minusAssign

Added in 1.5.0-alpha01
public final void minusAssign(@NonNull K key)

Removes the specified key and its associated value from the map.

minusAssign

Added in 1.5.0-alpha01
public final void minusAssign(@NonNull K[] keys)

Removes the specified keys and their associated value from the map.

minusAssign

public final void minusAssign(@NonNull Iterable<@NonNull K> keys)

Removes the specified keys and their associated value from the map.

minusAssign

Added in 1.5.0-alpha01
public final void minusAssign(@NonNull ObjectList<@NonNull K> keys)

Removes the specified keys and their associated value from the map.

minusAssign

Added in 1.5.0-alpha01
public final void minusAssign(@NonNull ScatterSet<@NonNull K> keys)

Removes the specified keys and their associated value from the map.

minusAssign

public final void minusAssign(@NonNull Sequence<@NonNull K> keys)

Removes the specified keys and their associated value from the map.

none

Added in 1.5.0-alpha01
public final boolean none()

Returns true if this cache has no entries.

plusAssign

public final void plusAssign(@NonNull Map<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

plusAssign

Added in 1.5.0-alpha01
public final void plusAssign(@NonNull ScatterMap<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

plusAssign

Added in 1.5.0-alpha01
public final void plusAssign(@NonNull SieveCache<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this map. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

plusAssign

public final void plusAssign(@NonNull Pair<@NonNull K, @NonNull V> pair)

Puts the key/value mapping from the pair in this cache, using the first element as the key, and the second element as the value. See put for more details about the insertion behavior.

plusAssign

public final void plusAssign(@NonNull Pair[] pairs)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

plusAssign

public final void plusAssign(@NonNull Iterable<@NonNull Pair<@NonNull K, @NonNull V>> pairs)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

plusAssign

public final void plusAssign(@NonNull Sequence<@NonNull Pair<@NonNull K, @NonNull V>> pairs)

Puts all the pairs into this map, using the first component of the pair as the key, and the second component as the value. Calling this * method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

put

Added in 1.5.0-alpha01
public final V put(@NonNull K key, @NonNull V value)

Adds value to the cache using the specific key. If key is already present in the map, the association is modified and the previously associated value is replaced with value. If key is not present, a new entry is added to the map. If an existing value is replaced, onEntryRemoved will be invoked with the evicted parameter set to false.

When value is added to the cache, sizeOf is invoked to query its size. If the total size of the cache, including the new value's size, is greater than maxSize, existing entries will be evicted. On each removal due to an eviction, onEntryRemoved will be invoked with the evicted parameter set to true.

Return the previous value associated with the key, or null if the key was not present in the cache.

putAll

public final void putAll(@NonNull Map<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

putAll

Added in 1.5.0-alpha01
public final void putAll(@NonNull ScatterMap<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from map into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

putAll

Added in 1.5.0-alpha01
public final void putAll(@NonNull SieveCache<@NonNull K, @NonNull V> from)

Puts all the key/value mappings in the from cache into this cache. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

putAll

public final void putAll(@NonNull Pair[] pairs)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

putAll

public final void putAll(@NonNull Iterable<@NonNull Pair<@NonNull K, @NonNull V>> pairs)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

putAll

public final void putAll(@NonNull Sequence<@NonNull Pair<@NonNull K, @NonNull V>> pairs)

Puts all the pairs into this cache, using the first component of the pair as the key, and the second component as the value. Calling this method is equivalent to calling put for each input pair. See put for more details about the behavior of each insertion.

remove

Added in 1.5.0-alpha01
public final V remove(@NonNull K key)

Removes the specified key and its associated value from the cache. If the key was present in the cache, this function returns the value that was present before removal, otherwise it returns null. On successful removal, sizeOf will be invoked to query the size of the removed element, and onEntryRemoved will be invoked with the evicted parameter set to false.

remove

Added in 1.5.0-alpha01
public final boolean remove(@NonNull K key, @NonNull V value)

Removes the specified key and its associated value from the cache if the associated value equals value. If the key was present in the cache, this function returns true, otherwise it returns false. On successful removal, sizeOf will be invoked to query the size of the removed element, and onEntryRemoved will be invoked with the evicted parameter set to false.

removeIf

Added in 1.5.0-alpha01
public final void removeIf(
    @NonNull Function2<@NonNull K, @NonNull V, @NonNull Boolean> predicate
)

Removes any mapping for which the specified predicate returns true.

resize

Added in 1.5.0-alpha01
public final void resize(@IntRange(from = 1, to = 2147483646) int maxSize)

Sets the maximum size of the cache to maxSize, in the unit defined by the implementation of sizeOf. The size must be strictly greater than 0. If the current total size of the entries in the cache is greater than the new maxSize, entries will be removed until the total size is less than or equal to maxSize. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.

set

Added in 1.5.0-alpha01
public final void set(@NonNull K key, @NonNull V value)

Adds value to the cache using the specific key. If key is already present in the cache, the association is modified and the previously associated value is replaced with value. If key is not present, a new entry is added to the map. If an existing value is replaced, onEntryRemoved will be invoked with the evicted parameter set to false.

When value is added to the cache, sizeOf is invoked to query its size. If the total size of the cache, including the new value's size, is greater than maxSize, existing entries will be evicted. On each removal due to an eviction, onEntryRemoved will be invoked with the evicted parameter set to true.

toString

public @NonNull String toString()

trimToSize

Added in 1.5.0-alpha01
public final void trimToSize(int maxSize)

Remove entries until the total size of the remaining entries is less than or equal to maxSize. The size of the entries is defined by the implementation of sizeOf. Upon each removal, onEntryRemoved is invoked with the evicted parameter set to true.

If maxSize is set to -1 (or any negative value), all entries are removed.