Implementing an LRU cache in JavaScript

An LRU or "Least Recently Used" cache stores a fixed-size collection of items ordered by how recently they were accessed. It is distinct from an LFU (Least Frequently Used) cache, which tracks access frequency.

This comes up quite often as an interview question, and though it's possible to implement the solution using an Array, the interviewer will most likely ask you to implement both get and put operations in such a way that the time complexity is constant time - O(1).

To solve this, we can use a Map as it offers us similar functionality to an Array, but with some performance benefits.

Difference between Map and Object

JavaScript Maps are similar to objects, with a few exceptions:

• The keys of a Map are ordered by the order of insertion.
• Creating a Map iterator and reading its first key are constant-time operations in common JavaScript engines. Iterating over every key is still O(n), as is Object.keys(obj), where n is the number of keys in the object.
• Getting the size of a Map is an O(1) operation (map.size), where Object.keys(obj).length is an O(n) operation.

Implementing the cache

We'll begin by creating a new LRUCache class with two instance properties:

1. The capacity of the cache
2. The cache itself

class LRUCache {
  constructor(capacity) {
    // Store the capacity size
    this.capacity = capacity;

    // Store the cache as a Map
    this.cache = new Map();
  }
}

Next we'll implement a get method on the class for retrieving a value in our cache by a particular key. If the key is not present in our cache, we should return -1.

get(key) {
  // Key does not exist, return -1
  if (!this.cache.has(key)) {
    return -1
  }

  // Temporarily store the value
  const value = this.cache.get(key)

  // Delete the key
  this.cache.delete(key)

  // Reinsert the key-value pair
  this.cache.set(key, value)

  // Return the value
  return value
}

You might be wondering why we delete the key every time we access it. A Map stores elements in insertion order, so deleting and reinserting the key-value pair moves it to the end of that order and marks it as the most recently used item.

put(key, value) {
  // If the key already exists, delete it so that it will be added
  // to the end of the Map as the most recently used item
  if (this.cache.has(key)) {
    this.cache.delete(key)
  }

  // Insert the key,value pair into cache
  this.cache.set(key, value)

  // If we've exceeded the cache capacity,
  // then delete the least recently accessed value,
  // which is the first item in the Map's insertion order
  if (this.cache.size > this.capacity) {
    const firstKey = this.cache.keys().next().value

    this.cache.delete(firstKey)
  }
}

Note here that map.keys() is not the same as Object.keys(obj). Where Object.keys(obj) returns an array of keys, while map.keys() returns a MapIterator. We can read the first key by calling .next().value on that iterator.

Using our class

const cache = new LRUCache(3);

// Insert 3 items to our cache
cache.put(1, 10); // Map { 1 => 10 }
cache.put(2, 20); // Map { 1 => 10, 2 => 20 }
cache.put(3, 30); // Map { 1 => 10, 2 => 20, 3 => 30 }

// Fetch by key
cache.get(2); // Returns 20, Map { 1 => 10, 3 => 30, 2 => 20 }

// Insert another item
cache.put(4, 40); // Map { 3 => 30, 2 => 20, 4 => 40 }
// Notice how our "1" key has been evicted