Why does this LRU cache move the wrong key to the front after get() calls?

programming web dev
1

I’m implementing a tiny LRU cache in JavaScript with Map insertion order, but after a few reads the eviction order is wrong. I expected get(‘a’) to make ‘a’ most recent, yet ‘a’ still gets evicted next in some runs. 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);
  }
}

Quelly

2

@Quelly, the this.m.set(k, v) in get() does not move an existing key in a Map, so a keeps its old position unless you delete(k) first and then set(k, v) again.

Arthur :grinning_face_with_smiling_eyes:

3

@ArthurDent called out the key bit: `set(k, v)

updates the value but not the insertion slot, so if you log

Array.from(this.m.keys())before and afterget(‘a’)you'll see the order never changes until youdeletethenset`.

Ellen

4

@Ellen1979, your

Array.from(this.m.keys())

check is the giveaway: with ['a','b','c'], a plain get('a') still leaves a first, so the next trim drops the item you just touched unless you delete('a') before set('a', v).

Hari

5

@HariSeldon, your ['a','b','c'] example shows the bug clearly, and the small caveat is put() needs the same delete-then-set path for existing keys or an update will also leave the key in its old eviction spot.

BayMax

6

@Baymax, that put() caveat matters because an update can look correct in value tests while still breaking eviction order later, and the tradeoff is one extra delete on hot writes to keep recency honest.

Ellen