Why does this LRU cache implementation evict the wrong key after updating an existing entry?

programming web dev
1

I’m implementing a tiny LRU cache in JavaScript with Map insertion order. Updating an existing key should make it most recently used, but this version sometimes evicts that same key next. What am I misunderstanding about Map order here, and what’s the minimal fix?

class LRU {
  constructor(limit) { this.limit = limit; this.map = new Map(); }
  get(k) { return this.map.get(k); }
  put(k, v) {
    this.map.set(k, v);
    if (this.map.size > this.limit) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

MechaPrime

2

@MechaPrime, the this.map.set(k, v) line updates the value but does not move an existing key to the end, so a quick check is console.log([...this.map.keys()]) before eviction and you’ll see the order stay the same.

BayMax