A cache that computes each key once
Write a cache over an expensive function. The requirement that makes this hard is not thread safety — it is that a key must be computed EXACTLY ONCE even when twenty threads ask for it at the same moment.
A synchronized map is thread-safe and computes it twenty times. A ConcurrentHashMap with get-then-put is thread-safe and also computes it twenty times. Neither is the answer.
Example
- input
20 threads request key "a" simultaneouslyoutputcompute() called onceAll twenty get the same value, and the expensive function ran a single time.
Constraints
- Reads of a warm key must not block.
- A failed computation must not be cached — the next caller retries.
Hints
Hint 1
computeIfAbsent holds a lock on the bin for the duration of the mapping function.
Hint 2
That is fine here and a deadlock if the function touches the same map. Know which you are doing.
Hint 3
The classic alternative is a map of Futures: put the promise first, compute after.
Stuck? The lesson behind this problem: 🧵 synchronized and volatile
java
Tab indents · Escape first to tab out
Test cases
These are the specification. Run tests checks your answer against them.
| Case | Input | Expected |
|---|---|---|
| 20 concurrent readers, one key | threads=20, key=a | compute calls = 1 |
| a warm key does not recompute | get(a) ×3 after warm | compute calls = 1 |
| a failure is not cached | compute throws once, then succeeds | compute calls = 2, value returned |