Build an LRU cache with LinkedHashMap

What you will learn

• Explain what an LRU cache is and why apps use one
• Turn on access order and use removeEldestEntry to keep a fixed size
• Write a reusable generic LruCache class and count hits and misses
• Cache a slow lookup and measure how many calls it saves
• Build an LRU cache with a HashMap and a doubly linked list

Topics in this lesson

1. The idea: least recently used
2. A reusable LruCache class
3. Caching a slow lookup
4. LRU without LinkedHashMap
5. Traps: loops and threads

Key points

• An LRU cache removes the entry that was used longest ago when it is full.
• new LinkedHashMap<>(16, 0.75f, true) keeps access order; override removeEldestEntry to return size() > capacity.
• The pattern is get, on a miss do the slow work, then put; the hit rate shows how useful the cache is.
• Without LinkedHashMap, use a HashMap plus a doubly linked list; get and put stay O(1).

Interview questions this lesson answers

• What is an LRU cache?
• How do you build an LRU cache with LinkedHashMap?
• What does the third constructor argument of LinkedHashMap do?
• When is removeEldestEntry called?
• How would you build an LRU cache without LinkedHashMap, and what is the cost?
• Is a LinkedHashMap cache thread-safe?
• Follow-up: what is the difference between LRU and LFU?