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