LRU cache implementation in Javascript

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 !== undefined) {
            // 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"

This:

https://github.com/monsur/jscache

seems to fit you case although setItem (i.e. put) is O(N) in the worst case, that happens if the cache is filled up on insertion. In this case the cache is searched to purge expired items or least recently used items. getItem is O(1) and the expiry is handled on the getItem operation (i.e. if the item being fetched is expired, removes it and returns null).

The code is compact enough to be easily understood.

P.S. It might be useful to add to the constructor the option to specify the fillFactor, which is fixed to 0.75 (meaning that when the cache is purged it's size is reduced at least to 3/4th of the maximum size)

This is worth a mention: https://github.com/rsms/js-lru

The core set of functions are O(1) and the code is heavily commented (with ASCII art too!)

The monsur.com implementation is O(n) on insertion only because it has items which actually expire on real world time. It is not a simple LRU. If you only care about maintaining the most recently used items without regard to real world time, this can be done in O(1). A queue, implemented as a doubly linked list, is O(1) for insertion or deletion from the end, and this is all you should need for a cache. As for lookup, a hash map, which javascript makes pathetically easy, should be good for nearly O(1) lookup (assuming the javascript engine uses a good hashmap, that's implementation dependent of course). So you have a linked list of items with a hash map pointing to the items. Manipulate the ends of the linked list as needed to put new items and requested items on one end and remove old items from the other end.

This library runtime-memcache implements lru and a few other caching schemes in javascript.

It uses modified Doubly Linked List to achieve O(1) for get, set and remove. You can check out the implementation which is pretty simple.

I improve @odinho's answer to fit this leetcode question

change if (item) to if (item != undefined) to fit value === 0 case

following is my code:

class LRUCache {
  constructor(max = 10) {
    this.max = max
    this.cache = new Map()
  }

  get(key) {
    let item = this.cache.get(key)
    if (item !== undefined) {
      // refresh key
      this.cache.delete(key)
      this.cache.set(key, item)
    }
    return item === undefined ? -1 : item
  }

  put(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
  }
}

It's not an LRU cache, but I've got my own linked map implementation. As it uses a JS objects as store, it'll have similar performance characteristics (the wrapper objects and hash function impart a performance penalty).

Currently, documentation is basically non-existant, but there's a related SO answer.

The each() method will pass the current key, the current value and a boolean indicating if there are more elements as arguments to the callback function.

Alternatively, looping can be done manually via

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}

I am aware that this is an old question but adding a link for future refrence. Check out https://github.com/monmohan/dsjslib . This has a LRU Cache implementation in addition to some other data structures. Such caches (and this one too) maintain doubly linked list of cache entries in LRU order i.e. entries move to the head as they are accessed and are removed from tail when they are reclaimed (say by expiry or because size limit was reached). Its O(1) since it only involves constant number of pointer manipulations.

Since we need read, write, update and delete operations in O(1), we use two data structures.

1. An Object(or Map)in JavaScript provides retrieval in O(1).
2. A Doubly LinkedList(Custom data structure we create) makes below functionalities in O(1)
   • change position of the most used element to the top
   • delete least used element from cache on reaching cache limit.

The custom implementation of Doubly LinkedList and Least Recently Used cache with clear explanation is given below.

https://medium.com/dsinjs/implementing-lru-cache-in-javascript-94ba6755cda9