Rafael Romão's Coding Labs

Lab L06 · Java + Go

Implementing an LFU cache

Build a fixed-capacity cache that, when full, evicts the key that has been used the fewest times; if several keys tie on that count, evict the one among them used least recently. Every hit (read or overwrite) increases a key's count. Both get and put should run in O(1) — no scanning all entries to find the victim.

The task

A map service caches rendered tiles. City-centre tiles are requested constantly; a tile in the middle of the ocean is requested once. With LRU, one burst of one-off requests can flush every hot tile. With LFU, a tile's history of popularity protects it. The classic O(1) design keeps key → entry, frequency → keys in recency order, and the current minimum frequency.

frequency buckets (each: least → most recent)freq 1e victimfreq 2acfreq 3xaget(a): move to tail of freq + 1minFrequency = 1 → evict first key of freq 1put(new) at capacity
Keys live in one bucket per frequency, each ordered from least to most recently used. The victim is always the first key in the minimum bucket; a hit moves a key to the tail of the next bucket.

What you implement

public final class LfuCache<K, V> {
    public LfuCache(int capacity);          // capacity <= 0 -> IllegalArgumentException
    public Optional<V> get(K key);          // hit: count + 1
    public void put(K key, V value);        // new key: count = 1; existing key: replace value, count + 1
}

Rules

  • A new key starts with frequency 1. A get hit or a put on an existing key adds 1 and makes the key the most recent within its new frequency.
  • A miss changes nothing.
  • Inserting a new key into a full cache first evicts: lowest frequency wins; among equal frequencies, the least recently used. Then the new key is inserted (so it is never its own victim).
  • Null key or value → NullPointerException. Methods are thread-safe.
  • O(1): Map<K, Entry> + Map<Long, LinkedHashSet<K>> (insertion order = recency) + a minFrequency field updated on touch and reset to 1 on insert.

Worked example

  1. capacity = 2. put(a), put(b) → both frequency 1.
  2. get(a) → a now 2. put(c) → evicts b (frequency 1). c starts at 1.
  3. get(c) → c now 2. put(d) → a and c both have 2; a was used longer ago → evict a.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: LfuCache.java · tests: LfuCacheTest.java. Go starter: cache.go · tests: cache_test.go.

cd java
./gradlew test --tests 'labs.lfucache.*'

cd go
go test -race -count=1 ./lfucache
Reveal the reference solutions

Java: LfuCache.java
Go: cache.go

When to use

Use this lab to explore a bounded in-memory cache that evicts the least frequently used entry. Each new entry starts at frequency one. A successful read or replacement increments frequency and marks the entry most recently used; a miss changes nothing. On insertion at capacity, evict the lowest frequency and, among ties, the oldest access. Capacity must be positive.

This is an instructional cache, not a durable or distributed system. The limit counts entries, not bytes, and returned mutable values are not copied or protected. Frequency buckets track access order without scanning all entries to choose an eviction victim.

Steps

  1. Define the state. Associate each key with a value, frequency, and membership in one ordered frequency bucket. A minimum-frequency field identifies the eviction bucket. Hold one lock for each complete public operation. Java rejects null keys and values; Go permits nil where the types allow it and returns a Boolean on lookup.
  2. Make ties observable. Insert A and B, then insert C without reading either: A is the older frequency-one entry and is evicted. If A is read first, B has the lower frequency and is evicted instead.
  3. Handle updates. Replacing a value counts as an access, so it updates both frequency and recency. Keys must have stable equality and hashing. Go rejects dynamically uncomparable keys and non-reflexive keys, such as NaN.
  4. Bound counters. Frequency saturates at the maximum representable value instead of wrapping. At saturation, further accesses move the entry to the newest end of that same bucket; recency breaks ties. Remove empty buckets so abandoned frequency values do not accumulate memory. There is no separate recency counter to wrap.
  5. Explain the trade-off. Lookup, replacement, and eviction are expected O(1), apart from key costs, map behavior, and contention. Go stores direct linked-list positions; Java uses insertion-ordered sets within each frequency. A promotion must update old membership, new membership, and the minimum together. Every key appears exactly once across the live buckets and once in the key map.
  6. Test boundaries. Check a miss, frequency-based eviction, recency ties, updating an existing entry, and counter boundaries. Add a reference model and controlled concurrent schedules before relying on this component in a demanding workload.

Checklist

Recall and variation

Rebuild bucket promotion before reading Go or Java. Variation: saturate an entry's frequency and access it again. Acceptance: it moves to the newest position in that bucket without wrapping, duplicating membership, or retaining empty buckets.

  • Capacity is positive and bounds the number of entries
  • A hit and an update count as accesses, while a miss does not
  • Eviction selects lowest frequency, then oldest recency
  • Frequencies saturate and empty buckets are removed
  • Mutable values and unbounded caller-owned memory are documented

Signals

Working: a short sequence of writes and reads predicts the exact eviction victim and replacement value.

Going wrong: map iteration decides a tie, frequency wraps to zero, or a promotion leaves stale membership in the old bucket.

Related