The idea here is, given a limit on the number of items to cache, how to choose the thing to evict that gives the best result.

In 1966 Laszlo Belady showed that the most efficient caching algorithm would be to always discard the information that will not be needed for the longest time in the future. This is a theoretical result that is unimplementable without domain knowledge. The Least Recently Used (LRU) algorithm is often used as a proxy. In general, it works well because of the locality of reference phenomenon and is the default in most caches.

A variation of LRU is the default eviction algorithm in Ehcache .

Ehcache provides three eviction algorithms to choose from for the memory store.

This is the default and is a variation on the Least Frequently Used algorithm.

The oldest element is the Less Recently Used element. The last-used timestamp is updated when an element is put into the cache or an element is retrieved from the cache with a get call.

This algorithm takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.

If probabilistic eviction does not suit your application, a true Least Recently Used deterministic algorithm is available by setting java -Dnet.sf.ehcache.use.classic.lru=true.

For each get() call on the element, the number of hits is updated. When a put() call is made for a new element (and assuming that the max limit is reached), the element with least number of hits (the Least Frequently Used element) is evicted.

If cache-element usage follows a Pareto distribution, this algorithm might give better results than LRU.

LFU is an algorithm unique to the Ehcache API. It takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.

Elements are evicted in the same order as they come in. When a put call is made for a new element (and assuming that the max limit is reached for the memory store) the element that was placed first (first-in) in the store is the candidate for eviction first-out.

This algorithm is used if the use of an element makes it less likely to be used in the future. An example here would be an authentication cache.

It takes a random sample of the Elements and evicts the smallest. Using the sample size of 15 elements, empirical testing shows that an Element in the lowest quartile of use is evicted 99% of the time.