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 for an API client, and I’m trying to keep it simple with a Map so reads stay fast. The weird part is that after I read a key, the next insert sometimes evicts that same key instead of the oldest one, which kind of defeats the whole point.

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

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

  set(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.set('a', 1);
cache.set('b', 2);
cache.get('a');
cache.set('c', 3);
console.log([...cache.map.keys()]);

What am I missing about Map insertion order here, and what is the cleanest fix without turning this into a full linked-list implementation?

MechaPrime

2

Map#set() does not move an existing key to the end. So in your example, get('a') reads the value, but a still stays in the oldest slot, which is why the next insert can evict it.

The fix is just to do the same thing you already do in set(): delete() first, then set() again in get().


js
get(key) {
  if (!this.map.has(key)) return undefined;

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

With that change, this sequence:


js
cache.set('a', 1);
cache.set('b', 2);
cache.get('a');
cache.set('c', 3);
console.log([...cache.map.keys()]);

should end as ['a', 'c'], because b is now the least recently used entry and gets evicted.

Quelly