Designing an O(1) Least Recently Used Cache with JavaScript Map

A Least Recently Used (LRU) Cache discards the least recently accessed items when the cache reaches capacity. In traditional computer science implementations, an LRU cache requires pairing a Hash Table (for (O(1)) lookups) with a Doubly Linked List (for (O(1)) pointer adjustments).

In modern JavaScript, the built-in Map object preserves key-value insertion order, providing a clean way to implement an LRU cache in few lines of code.

Example #

const cache = new LRUCache(2);
cache.put('a', 1);
cache.put('b', 2);
console.log(cache.get('a')); // 1 ('a' becomes most recently used)
cache.put('c', 3);          // Evicts 'b'
console.log(cache.get('b')); // -1 (null)

Implementation #

When an item is accessed via .get() or updated via .put(), we refresh its recency by deleting and re-inserting the key into the Map:

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    // Refresh recency
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      // Evict oldest (first key in map iterator)
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
    this.map.set(key, value);
  }
}

Main Point: JavaScript's Map retains insertion order, allowing (O(1)) LRU cache eviction and recency updates by re-inserting accessed entries.

Credits #

Photo by Simone Hutsch on Unsplash

← Home