Notes
Requirements
The requirements. Get, put and remove by key. A put can carry its own time to live, or fall back to a default, and an expired entry must never be returned. The cache holds at most N entries; when it is full, a policy chosen at construction, LRU or LFU, picks the victim. Get and put must be constant time, the cache is shared by many threads, and we want hit and miss counts.
Pin down the edge cases. A time to live of zero means the entry never expires. Putting an existing key replaces the value and restarts its clock. If the cache is full but some entries have already expired, drop those before evicting a live one. When two keys tie in LFU, evict the least recently used of them. And capacity counts entries for now; sizing by bytes is a follow-up.
- get(key), put(key, value)
- put with a TTL, or a default
- remove(key)
- capacity: at most N entries
- full? evict by policy:
- LRU or LFU, chosen at build
- expired entries never returned
- O(1) get and put
- safe from many threads
- hit and miss counts
- TTL of 0?
- never expires
- put on an existing key?
- replace value, reset TTL
- full but some entries expired?
- drop expired before evicting
- LFU tie?
- least recently used of them
- capacity by count or bytes?
- count, bytes later
Entities
Four collaborators do all the work. A hash map from key to entry gives constant-time lookups. An eviction policy tracks the order of keys and names the victim. A clock tells the cache what time it is, injected so tests can fake it. And a lock keeps the map and the policy consistent with each other. Separating the map from the policy is what lets us swap LRU for LFU without touching the cache.
Class diagram
Each map value is a small immutable entry: the value and an absolute expiry time in milliseconds, with zero meaning never. Storing the absolute time, not the duration, makes the expiry check a single comparison against the clock. A replaced value gets a brand new entry, so there is never a half-updated entry for another thread to see.
record Entry<V>(V value, long expiresAt) {
boolean expired(long now) {
return expiresAt > 0
&& now >= expiresAt;
}
}
Map<K, Entry<V>> map = new HashMap<>()
EvictionPolicy<K> policy
LongSupplier clock
ReentrantLock lock Strategy: eviction
Eviction is a Strategy. The cache tells the policy about three events, a put, a get and a remove, and asks it one question: who is the victim? LRU, LFU, first in first out, or random eviction all fit the same four methods. The policy is not thread-safe on its own, deliberately, because the cache already holds its lock whenever it calls the policy.
interface EvictionPolicy<K> {
void onPut(K key);
void onGet(K key);
void onRemove(K key);
K victim();
}
LRU, LFU, FIFO, random:
same four methods LRU in O(1)
LRU in constant time is a hash map plus a doubly linked list: on every use, unlink the key and append it at the back; the front is always the least recently used. Java's linked hash set is exactly that pair, so on a get we remove and re-add the key, and the victim is the first element. In the demo, after putting a, b, c and reading a, putting d evicts b. In an interview, offer to write the linked list by hand too.
LinkedHashSet<K> order
onGet(k): order.remove(k);
order.add(k) // to the back
onPut(k): same as onGet
victim(): order.iterator().next()
put a, b, c; get a; put d
order: b, c, a -> evict b LFU in O(1)
LFU in constant time is the clever one. Keep each key's use count, and a bucket of keys for each count, where each bucket is ordered by recency. Track the smallest count in use. A new key goes in bucket one and resets the minimum to one. A get moves the key up one bucket, and if it emptied the minimum bucket, the minimum goes up by one. The victim is the oldest key in the minimum bucket, which also breaks ties by recency.
Map<K, Integer> freq Map<Integer, LinkedHashSet<K>> buckets int minFreq onPut new: freq 1, bucket 1, min = 1 onGet: move key from bucket f to f+1 bucket f empty and f == min: min++ victim(): first of buckets[minFreq] (oldest in that bucket: LRU tie)
TTL expiry
Expiry happens in two ways. Lazy expiry checks the expiry time on every get and removes a dead entry before answering, so an expired value is never returned and it costs nothing extra. But a key nobody reads would sit in memory forever, so a background sweeper calls sweep every second or so. And when a put finds the cache full, it purges expired entries first, so a live entry is only evicted when it truly has to be.
- lazy: get() checks expiresAt
- and removes a dead entry
- cost: nothing extra
- active: a sweeper calls sweep()
- every second or so
- frees cold keys nobody reads
- put when full: purge expired
- before evicting a live entry
- big caches: sample, not scan
Flow: put when full
The put flow. Take the lock. If the key is new and the cache is full, first purge expired entries, and if it is still full, ask the policy for a victim and remove it from both the map and the policy. Then store the new entry with its expiry time and tell the policy about the put. Release the lock, and only then call the removal listeners, so a slow listener never holds up other threads.
lock
if new key and size == capacity:
purgeExpired(now)
still full? remove(policy.victim())
map.put(key, new Entry(v, now + ttl))
policy.onPut(key)
unlock
run queued listener events Flow: get
The get flow. Under the lock, look up the entry. If it has expired, remove it and treat it as missing. A miss increments the miss counter and returns an empty optional. A hit increments the hit counter and tells the policy, which moves the key to the back for LRU or up a bucket for LFU. Returning an optional instead of null makes the caller handle the miss on purpose.
lock e = map.get(key) if e expired: remove it, e = null e == null: misses++, empty else: hits++, policy.onGet(key) unlock return Optional.of(value) or empty
Concurrency
Concurrency has a trap. It is tempting to use a read-write lock so many readers can get at once. But a get is not read-only: LRU moves the key, LFU bumps its count, and expiry may remove it. So every get needs the write lock, and a read-write lock buys nothing. One plain reentrant lock is correct and simple, and holds for well under a microsecond. Hit and miss counters use LongAdder, which needs no lock at all.
If one lock becomes the bottleneck at very high throughput, there are three standard moves. Stripe the cache into, say, sixteen segments, each with its own map, policy and lock, chosen by the key's hash; the cost is that LRU becomes per segment. Or record gets in a buffer and apply the reordering in batches, which is what production Java caches do. Or approximate: sample five random keys and evict the oldest, as some key-value stores do.
- get() is not read-only:
- LRU moves the key, LFU bumps
- its count, expiry may remove
- so get needs the write lock
- and a RW lock buys nothing
- one ReentrantLock: correct,
- simple, ~100 ns per call
- LongAdder for stats: no lock
- striping: 16 segments, each
- its own map, policy, lock;
- segment = hash(key) % 16
- LRU becomes per segment
- buffer reads: record gets in a
- queue, apply them in batches
- sampled eviction: pick the
- oldest of 5 random keys
- (approximate, lock-free)
Observer
Removal listeners are the Observer pattern. When an entry is evicted or expires, the cache queues an event with the key, the value and the cause, and runs the listeners after releasing the lock. A metrics listener counts evictions, a write-behind listener saves dirty values to a database, and a debugging listener logs them. The cache never needs to know what any of them do.
Factory
Callers should not construct policy objects themselves, because a policy instance must never be shared between two caches. A small factory maps a policy enum to a fresh instance, so creating a cache reads like a sentence: capacity a hundred, default time to live five seconds, LFU, and the system clock. In a larger codebase this grows into a builder with optional settings like a maximum weight or a loader.
enum Policy { LRU, LFU }
static <K> EvictionPolicy<K>
policyFor(Policy p) {
return switch (p) {
case LRU -> new LruPolicy<>();
case LFU -> new LfuPolicy<>();
};
}
new InMemoryCache<>(100, 5_000,
Policy.LFU, System::currentTimeMillis) Testing
The full code is below the player. The demo checks LRU evicts b, LFU evicts the least used key c, and that a five-second entry is still there after four seconds and gone after six, while a never-expiring key survives. The clock is a long supplier backed by an atomic counter, so the test moves time instantly. Finally eight threads hammer one cache, and it never grows past its capacity.
[lru] evicted: b LRU has b? false, has a? true [lfu] evicted: c LFU has c? false, has a? true After 4 s: token [ttl] expired: session:42 After 6 s: gone, config v7 Shared cache: hits=.. misses=.. size=100 (8 threads)
Follow-ups
Expect follow-ups. Write LRU without library classes: a hash map pointing into a doubly linked list with sentinel nodes. LRU or LFU? LFU keeps stable hot keys, LRU adapts faster when access patterns shift. Capacity in bytes? Add a weigher function. Many threads missing the same key at once? Keep one loading future per key so only one loads. And distributing it across machines is consistent hashing, covered in the system design track.
- write LRU without libraries?
- map + doubly linked list
- LRU vs LFU: when?
- LFU for stable hot keys,
- LRU for shifting access
- capacity in bytes? a weigher
- thundering herd on a miss?
- one loader per key (futures)
- distributed? consistent hashing
Say it like this
The short version. A hash map of entries that carry an absolute expiry time, plus an eviction strategy: LRU as an access-ordered set, LFU as frequency buckets with a minimum. Expiry is lazy on get plus a background sweeper. One lock guards both, because even a get changes the order; stripe the cache if that lock gets hot, and run listeners outside it.
- "A hash map of entries with an
- absolute expiry time, and an
- eviction strategy: LRU as an
- access-ordered set, LFU as
- frequency buckets with a min.
- Lazy expiry on get plus a
- sweeper. One lock, because get
- mutates order; stripe if hot."