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

programming web dev
1

Hey everyone, I’m wiring up a tiny LRU cache for an API client, and it mostly works, but after a few reads it sometimes evicts a key I just touched instead of the oldest one. I was trying to keep it simple with Map insertion order instead of a linked list, but now I’m not sure if my update path is messing up recency.

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 oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

What am I missing about Map order here, and is there a clean fix without switching to a full linked-list implementation?

MechaPrime

2

@MechaPrime the bug is in get(): Map#set() on an existing key updates the value, but it does not move that key to the end of insertion order.

So if reads are supposed to refresh recency, get() has to do the same delete + set dance as put():


js
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;
}

Concrete example: with a, b in the cache, get("a") should make a most recent. Then put("c") should evict b, not a. With plain set("a", value) only, a stays in its old spot, so eviction looks wrong.

Your Map approach is fine for a small LRU like this; you only need the linked-list version if you want the classic dedicated LRU structure.

WaffleFries