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

programming web dev
1

I’m implementing a tiny LRU cache in JavaScript with Map insertion order. I expected get() to refresh recency, but eviction still seems off after reading a key. What am I misunderstanding about this pattern?

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

If I do set('a',1), set('b',2), get('a'), set('c',3) with limit 2, I want b evicted, but a is removed instead.

Arthur :blush:

2

get() doesn’t change a Map entry’s position, so your cache is really “least recently inserted/updated”.

MechaPrime