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

programming web dev
1

Hey everyone, I’m working on a small LRU cache in JavaScript for interview practice, and the weird part is it mostly works until I read a key and then add one more item. I wanted O(1) behavior, but right now it feels like my recency update is fighting the eviction logic.

class LRU {
  constructor(limit) {
    this.limit = limit;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);

    if (this.map.size > this.limit) {
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
  }
}

const cache = new LRU(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");
cache.put("c", 3);
console.log([...cache.map.keys()]);

Why is this still evicting the wrong key after get("a"), and what is the cleanest way to make the recency update reliable?

Sora

2

Your get() is currently doing an overwrite on the existing Map entry, not a recency move to the newest position.

Map preserves insertion order, and calling set() on an existing key does not move it. Since eviction removes this.map.keys().next().value, "a" still looks oldest unless you remove it first and re-insert it.

The smallest fix is this:

this.map.delete(key);
this.map.set(key, value);
get(key) {
  if (!this.map.has(key)) return -1;

  const value = this.map.get(key);
  this.map.delete(key);
  this.map.set(key, value);
  return value;
}

That this.map.delete(key) before this.map.set(key, value) is the whole trick.

  • delete(key) removes the old insertion position for "a".
  • set(key, value) re-adds it at the end, which ensures keys().next().value is the true least-recent key.

So after get("a"), b becomes the one that gets evicted.

Using your cache example, it should behave like this:

class LRU {
  constructor(limit) {
    this.limit = limit;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;

    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    }

    this.map.set(key, value);

    if (this.map.size > this.limit) {
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
  }
}

const cache = new LRU(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");      // 1
cache.put("c", 3);   // evicts "b"

console.log([.cache.map.keys()]); // ["a", "c"]

Tiny practical snippet: if you want less duplication, make a small touch(key) helper and call it from both get() and the update path in put().

Yoshiii

3

@Yoshiii’s touch(key) idea is the bit I’d keep, because the tradeoff is a tiny helper buys you fewer “fixed get, forgot put” bugs later.

Arthur :smiling_face_with_sunglasses:

Arthur

4

Arthur, that touch(key) helper matters because the easy miss is put on an existing key should also refresh recency, otherwise updating "b" and then inserting "c" can still evict "b" if only get does the move.

Quelly

5

@Quelly calling out the existing-key put("b", .) case is the useful gotcha, because Map#set won’t move "b" unless you delete first, so a shared touch() keeps both read and overwrite paths honest.

WaffleFries