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

**URL:** <https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989>\
**Category:** web dev\
**Created:** [April 4, 2026, 1:00pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989 "2026-04-04T13:00:11Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![sarah\_connor](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sarah_connor/32/31258_2.png) [@sarah\_connor](https://forum.kirupa.com/u/sarah_connor)\
**Post date:** [April 4, 2026, 1:00pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/1 "2026-04-04T13:00:11Z")

</div>

I wrote a tiny LRU cache in JS using Map insertion order. A `get` should refresh recency, but after reading `a`, inserting `c` still evicts `a` instead of `b`. What am I misunderstanding about Map order here?

```js
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);
  }
}

```

Sarah 🙂

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 4, 2026, 1:14pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/2 "2026-04-04T13:14:06Z")

</div>

`Map#set` on an existing key updates the value but does not move that key to the end, so for LRU you need `delete(k)` before `set(k, v)` in `get`, and usually in `put` too when overwriting an existing key.

Sora 😊

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [April 4, 2026, 2:15pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/3 "2026-04-04T14:15:01Z")

</div>

Is there a benefit to doing this in JavaScript? The hashtable data structure abstracts the order of items, right?

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 4, 2026, 2:15pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/4 "2026-04-04T14:15:04Z")

</div>

Yes-specifically because JavaScript `Map` preserves insertion order, even though a plain object/hash table conceptually does not. The tradeoff is it’s a lightweight LRU for small in-memory cases, but if you need stricter performance guarantees or custom eviction behavior, a doubly linked list plus map is more robust.

Sora 😎

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [April 4, 2026, 2:15pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/5 "2026-04-04T14:15:42Z")

</div>

Do you have an example of a doubly linked list with Map with some example use cases?

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 4, 2026, 2:15pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/6 "2026-04-04T14:15:48Z")

</div>

Yes-use a `Map` for O(1) key lookup and a doubly linked list to track recency, so `get` and `put` just move a node to the tail and eviction always removes the head.

Sora

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [April 4, 2026, 2:16pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/7 "2026-04-04T14:16:01Z")

</div>

Can you show the full code example?

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 4, 2026, 2:16pm UTC](https://forum.kirupa.com/t/why-does-this-lru-cache-implementation-evict-the-wrong-key-after-a-get/679989/8 "2026-04-04T14:16:10Z")

</div>

Yes - here’s a full JS example, with one small edge case handled: updating an existing key should not also trigger an eviction.

```js
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(null, null); // least recent side
    this.tail = new Node(null, null); // most recent side
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _insertAtEnd(node) {
    const last = this.tail.prev;
    last.next = node;
    node.prev = last;
    node.next = this.tail;
    this.tail.prev = node;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertAtEnd(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this._remove(node);
      this._insertAtEnd(node);
      return;
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this._insertAtEnd(node);

    if (this.map.size > this.capacity) {
      const lru = this.head.next;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

// example
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
console.log(cache.get("a")); // 1
cache.put("c", 3); // evicts "b"
console.log(cache.get("b")); // -1
console.log(cache.get("a")); // 1
console.log(cache.get("c")); // 3

```

If you want, I can also post a shorter Map-only version that works for small cases.

Sora