Eviction policies: LRU and TTL
45 min · Intermediate
Eviction is removing entries from a full cache to make room for new ones. The eviction policy decides which entry goes; LRU (least recently used) is the one you will use and be asked about most, and TTL expiry removes entries that are too old.
Topics in this lesson
- Why caches need eviction
- LRU, LFU and FIFO compared
- LRU with LinkedHashMap
- LRU from scratch: HashMap plus doubly linked list
- Combining an LRU size limit with TTL
Key points
- A cache without eviction grows until it runs out of memory; a bounded cache evicts by a policy.
- FIFO evicts the oldest insert, LRU the least recently used, LFU the least often used; LRU is the usual default.
new LinkedHashMap<>(16, 0.75f, true)plusremoveEldestEntryreturningsize() > capacityis an LRU cache (not thread-safe).- From scratch:
HashMap<K, Node>plus a doubly linked list gives O(1)getandput; addexpiresAtfor TTL.
Interview questions this lesson answers
- How does an LRU cache work?
- How would you implement LRU in Java quickly?
- Implement LRU with O(1) get and put without LinkedHashMap.
- What is the difference between LRU and LFU?
- What is the difference between LRU eviction and TTL expiry?
- Is a LinkedHashMap LRU safe to share between threads?
- Your cache hit ratio is low. How do you tell if it is too small or the TTL is too short?
Sign in to continue this lesson
Create an account to read every lesson, practise with the exercises and keep track of your progress.