LRU Cache
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints indicate automated detection is 'no' and the sole listed tool is Blackfire (a profiler), meaning misuse — such as unbounded growth, O(n) eviction, or missing linked-list pairing — only surfaces under profiling or careful code review. The code_pattern describes subtle structural bugs not caught by linters or compilers.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix points to combining SplDoublyLinkedList with an associative array, and common_mistakes reveal multiple interrelated issues (lookup structure, eviction order, update handling). Correcting a naive O(n) array-based implementation or a hash-map-only implementation requires rethinking the data structure design and touching the cache component meaningfully, though it's generally contained to one component rather than cross-cutting.
Closest to 'localised tax' (b3). The LRU cache applies to web, CLI, and queue-worker contexts but is typically an isolated cache component. Its structural complexity (hash map + linked list) is a local burden on the developer implementing or maintaining that component, without strongly shaping the rest of the codebase.
Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception field identifies that LRU is assumed to be universally optimal, but LFU outperforms it for burst-heavy access patterns. Additionally, common_mistakes show developers frequently assume a hash map alone is sufficient, missing the linked-list requirement. These are well-documented gotchas that competent developers encounter and eventually learn, placing this firmly at t5.
Also Known As
TL;DR
Explanation
An LRU cache maintains both O(1) lookup (hash map) and O(1) eviction order tracking (doubly linked list). The list represents access order — most recent at the head, least recent at the tail. On access, an entry moves to the head. When the cache is full, the tail entry is evicted. This combination is the classic example of using two data structures together to achieve better complexity than either alone.
Diagram
flowchart LR
subgraph LRU Cache - capacity 3
Q[most recent] -->|doubly linked| B[B] --> C[C] -->|least recent| D[D]
MAP[(HashMap<br/>key to node<br/>O of 1 lookup)]
end
ACCESS[Access B] -->|move to front| Q2[B] --> A2[A] --> C2[C]
INSERT[Insert E - cache full] --> EVICT[Evict D - least recently used]
INFO[O of 1 get and put<br/>HashMap for lookup<br/>Doubly linked list for order]
style MAP fill:#1f6feb,color:#fff
style EVICT fill:#f85149,color:#fff
style INFO fill:#238636,color:#fff
Common Misconception
Why It Matters
Common Mistakes
- Using a plain array for LRU — O(n) lookup defeats the purpose.
- Not understanding that a hash map alone cannot implement LRU in O(1) — you also need the linked list for eviction order.
- PHP's SplDoublyLinkedList does not provide hash-based lookup — combine with an array for a true O(1) LRU.
- Not handling the case where a key is updated — it should move to the head, not create a duplicate.
Code Examples
// Naive LRU — O(n) eviction:
class NaiveCache {
private array $cache = [];
public function get(string $key): mixed {
if (isset($this->cache[$key])) {
$val = $this->cache[$key];
unset($this->cache[$key]);
$this->cache[$key] = $val; // O(n) reorder
return $val;
}
return null;
}
}// O(1) LRU — array (hash map) + SplDoublyLinkedList:
class LRUCache {
private array $map = [];
private SplDoublyLinkedList $list;
private int $capacity;
public function __construct(int $cap) {
$this->capacity = $cap;
$this->list = new SplDoublyLinkedList();
}
// get() moves node to front; put() evicts tail if full
}