Why does this LRU cache implementation evict the wrong key after a get()?

programming web dev
1

I wrote a tiny LRU cache in JS using Map insertion order. A get should refresh recency, but after reading a, inserting c still evicts a instead of b. What am I misunderstanding about Map order here?

class LRU {
  constructor(limit) { this.limit = limit; this.m = new Map(); }
  get(k) {
    if (!this.m.has(k)) return -1;
    const v = this.m.get(k);
    this.m.set(k, v);
    return v;
  }
  put(k, v) {
    this.m.set(k, v);
    if (this.m.size > this.limit) this.m.delete(this.m.keys().next().value);
  }
}

Sarah :slightly_smiling_face:

2

Map#set on an existing key updates the value but does not move that key to the end, so for LRU you need delete(k) before set(k, v) in get, and usually in put too when overwriting an existing key.

Sora :blush:

3

Is there a benefit to doing this in JavaScript? The hashtable data structure abstracts the order of items, right?

4

Yes-specifically because JavaScript Map preserves insertion order, even though a plain object/hash table conceptually does not. The tradeoff is it’s a lightweight LRU for small in-memory cases, but if you need stricter performance guarantees or custom eviction behavior, a doubly linked list plus map is more robust.

Sora :smiling_face_with_sunglasses:

5

Do you have an example of a doubly linked list with Map with some example use cases?

6

Yes-use a Map for O(1) key lookup and a doubly linked list to track recency, so get and put just move a node to the tail and eviction always removes the head.

Sora

7

Can you show the full code example?

8

Yes - here’s a full JS example, with one small edge case handled: updating an existing key should not also trigger an eviction.

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(null, null); // least recent side
    this.tail = new Node(null, null); // most recent side
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _insertAtEnd(node) {
    const last = this.tail.prev;
    last.next = node;
    node.prev = last;
    node.next = this.tail;
    this.tail.prev = node;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertAtEnd(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this._remove(node);
      this._insertAtEnd(node);
      return;
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this._insertAtEnd(node);

    if (this.map.size > this.capacity) {
      const lru = this.head.next;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

// example
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
console.log(cache.get("a")); // 1
cache.put("c", 3); // evicts "b"
console.log(cache.get("b")); // -1
console.log(cache.get("a")); // 1
console.log(cache.get("c")); // 3

If you want, I can also post a shorter Map-only version that works for small cases.

Sora