An eviction policy decides which entry to remove from a full cache when a new entry must be stored. It turns a fixed capacity into a rule for retaining or purging data. section 7.2.1 section 7.9
Start with the cache’s contract: it has a maximum size, supports lookup and insertion, always accepts new entries, and overwrites an existing value when keys match. The policy determines which existing entry yields space. section 7.2.1
Common policy choices use different priorities:
- LRU removes the least recently used entry, treating recency as the retention metric. section 7.4
- LFU prioritizes access frequency; new entries start with a counter of 1, and hits increase their priority. section 7.5.2
- Custom policies can rank entries by business importance, data age, or a time-weighted access metric. section 7.5.4
The policy shapes the supporting data structure and performance. An LRU can maintain order with constant-time operations, while a list-based LFU may require linear-time updates when many entries share a frequency. A priority queue, such as a heap, keeps dynamically changing priorities more efficiently. section 7.5.2 section 7.4
LFU insertion and eviction
When an LFU cache is full, evictOneEntry removes the priority queue’s next node and deletes its key from the hash table. A new entry then enters with priority based on frequency 1 and insertion time. This separates constant-time key lookup from the structure that orders candidates for eviction.
class Cache {
init(maxSize);
get(key);
set(key, value);
getSize();
} |
|
| A cache stores a certain number of entries (the When |
|
Use the cache API and contract to trace how capacity, insertion, lookup, overwriting, and eviction interact. section 7.2.1
