Mastering LRU Cache: From Theory to a High‑Performance JavaScript Implementation

1. Introduction

Vue SSR brings SEO and fast content delivery but incurs heavy performance costs because creating component instances and virtual‑DOM nodes is far slower than string‑based templating. To mitigate this, the author adopts an LRU (Least Recently Used) cache to improve response time and service load.

2. Cache Overview

Purpose : Temporarily store expensive computation or data‑fetch results so subsequent requests can retrieve them directly, reducing resource consumption and latency.

Types : Local cache (in‑process, fast, no inter‑process communication) and distributed cache (e.g., Redis, a separate service shared among multiple applications).

Eviction Rules : When storage limits are reached, common algorithms include FIFO, LRU, and LFU. The article focuses on LRU, which discards the least recently accessed entry.

3. Understanding LRU

The LRU rule assumes that data not accessed recently is unlikely to be needed soon; therefore, when the cache is full, the oldest entry is removed.

Visualization: imagine an ordered list where new or recently accessed keys move to the tail; the head holds the least‑used key.

4. Simple LRU with JavaScript Map

Because Map preserves insertion order, a minimal LRU can be built by deleting the first key when the cache exceeds its size limit and re‑inserting the accessed key to move it to the tail.

class Cache {</code><code>    constructor(options = { max: 5 }) {</code><code>        this.max = options.max;</code><code>        this.cache = new Map();</code><code>    }</code><code>    set(key, value) {</code><code>        if (this.cache.has(key)) {</code><code>            this.cache.delete(key);</code><code>        }</code><code>        if (this.cache.size >= this.max) {</code><code>            this.cache.delete(this.cache.keys().next().value);</code><code>        }</code><code>        this.cache.set(key, value);</code><code>    }</code><code>    get(key) {</code><code>        if (this.cache.has(key)) {</code><code>            const val = this.cache.get(key);</code><code>            this.cache.delete(key);</code><code>            this.cache.set(key, val);</code><code>            return val;</code><code>        }</code><code>        return null;</code><code>    }</code><code>}

This works because Map.keys() returns an iterator ordered by insertion, allowing O(1) removal of the oldest entry.

5. Building a Full‑Featured LRU Cache

Requirements :

Configurable maximum length.

Public get and set methods with O(1) time complexity.

Automatic eviction of the least‑used entry when capacity is exceeded.

Design Choice : Combine a hash table (JavaScript Map) for fast key lookup with a doubly‑linked list stored in parallel arrays ( prev, next) to maintain LRU order. An auxiliary free array records reclaimed indices.

Key operations: #createNewIndex(): Returns an index for a new entry, reusing freed slots or evicting the head when the cache is full. #moveToTail(index): Moves an existing node to the tail of the list. #connect(prev, next): Relinks two neighboring nodes.

6. Complete Implementation

class Cache {</code><code>    constructor(options) {</code><code>        const { max = 5, ttl = 0 } = options || {};</code><code>        if (!max) throw new Error('Length must be greater than 0');</code><code>        this.max = max;</code><code>        this.ttl = ttl;</code><code>        this.keyMap = new Map();</code><code>        this.keyList = new Array(this.max).fill(null);</code><code>        this.valList = new Array(this.max).fill(null);</code><code>        this.prev = new Array(this.max);</code><code>        this.next = new Array(this.max);</code><code>        this.free = [];</code><code>        this.head = 0;</code><code>        this.tail = 0;</code><code>        this.size = 0;</code><code>        this.fill = 1;</code><code>    }</code><code>    set(key, value, ttl = this.ttl) {</code><code>        let index = this.keyMap.get(key);</code><code>        if (index === undefined) {</code><code>            index = this.#createNewIndex();</code><code>            this.keyList[index] = key;</code><code>            this.valList[index] = { value, expire: ttl ? Date.now() + ttl * 1000 : -1 };</code><code>            this.keyMap.set(key, index);
            this.next[this.tail] = index;</code><code>            this.prev[index] = this.tail;</code><code>            this.tail = index;</code><code>            this.size++;</code><code>        } else {</code><code>            const oldVal = this.valList[index];</code><code>            if (value !== oldVal) this.valList[index] = value;</code><code>            this.#moveToTail(index);
        }</code><code>    }</code><code>    get(key) {</code><code>        const index = this.keyMap.get(key);
        if (index === undefined) return null;
        const now = Date.now();
        const entry = this.valList[index];
        if (entry.expire !== -1 && now > entry.expire) {</code><code>            this.delete(key);
            return null;
        }
        this.#moveToTail(index);
        return entry.value;
    }</code><code>    delete(key) {</code><code>        const index = this.keyMap.get(key);
        if (index === undefined) return false;
        if (this.size === 1) { this.clear(); return true; }
        this.keyMap.delete(key);
        this.valList[index] = null;
        this.keyList[index] = null;
        this.free.push(index);
        this.size--;
        if (index === this.head) this.head = this.next[index];
        else if (index === this.tail) this.tail = this.prev[index];
        else this.#connect(this.prev[index], this.next[index]);
        return true;
    }</code><code>    clear() {</code><code>        this.keyMap.clear();
        this.valList.fill(null);
        this.keyList.fill(null);
        this.head = this.tail = 0;
        this.fill = 1;
        this.free = [];
        this.size = 0;
    }</code><code>    #createNewIndex() {</code><code>        if (this.size === 0) return this.tail;
        if (this.size === this.max) {</code><code>            const oldKey = this.keyList[this.head];
            this.keyMap.delete(oldKey);
            const oldHead = this.head;
            this.head = this.next[oldHead];
            this.size--;
            return oldHead;
        }
        if (this.free.length) return this.free.pop();
        return this.fill++;
    }</code><code>    #moveToTail(index) {</code><code>        if (index === this.tail) return;
        if (index === this.head) this.head = this.next[index];
        else this.#connect(this.prev[index], this.next[index]);
        this.#connect(this.tail, index);
        this.tail = index;
    }</code><code>    #connect(prev, next) { this.prev[next] = prev; this.next[prev] = next; }</code><code>}

7. Verification

Using the cache with a series of set operations ( a ‑ f, then updating b) produces the expected order, which matches the diagrams shown in the article. Browser console screenshots confirm the behavior.

8. Conclusion

By combining a hash table for O(1) lookups with a doubly‑linked list stored in arrays, the presented LRU cache achieves constant‑time get and set operations without any linear scans. The approach is applicable to SSR services, API layers, or any JavaScript environment where cache‑driven performance gains are needed.