LRU cache implementation in Javascript

Question

Java has LinkedHashMap which gets you 99% there to an LRU cache.

Is there a Javascript implementation of an LRU cache, preferably from a reputable source, that is:

1. understandable
2. efficient (amortized O(1) get/put/delete)

? I've been searching on the web but couldn't find one; I thought I found one on Ajax Design Patterns but it glosses over the sendToTail() method and has O(n) performance (presumably, since the queue and associative array are split up).

I suppose I could write my own, but I've learned the hard way that reinventing the wheel for core algorithms can be hazardous to one's health :/

Answer 1

Map should be O(1) in most implementations average case. Since Map keeps insertion order, adding a bit of code around it will get you a LRU and for most uses this should be plenty fast.

I needed a simple LRU cache for a small number of expensive operations (1 second). I felt better about copy-pasting some small code rather than introducing something external, but since I didn't find it I wrote it:

class LRU {     constructor(max = 10) {         this.max = max;         this.cache = new Map();     }      get(key) {         let item = this.cache.get(key);         if (item) {             // refresh key             this.cache.delete(key);             this.cache.set(key, item);         }         return item;     }      set(key, val) {         // refresh key         if (this.cache.has(key)) this.cache.delete(key);         // evict oldest         else if (this.cache.size == this.max) this.cache.delete(this.first());         this.cache.set(key, val);     }      first() {         return this.cache.keys().next().value;     } } 

Usage:

> let cache = new LRU(3) > [1, 2, 3, 4, 5].forEach(v => cache.set(v, 'v:'+v)) > cache.get(2) undefined > cache.get(3) "v:3" > cache.set(6, 6) > cache.get(4) undefined > cache.get(3) "v:3"