How To Implement LRU Cache In JavaScript In 28 Lines Or Less

LRU stands for Least Recently Used. It is a cache algorithm that is used to determine which elements should be discarded from memory when the cache is full.

The most basic LRU algorithm would simply check the last time a given value was accessed and keep the least recently used element. However, this can lead to poor performance as it does not take into account other factors such as the frequency of access or how recently an item was used.

LRU Cache implementation is very easy and simple. In this post we will implement a LRU Cache using a single Map to store. The steps required to implement the LRU Cache are as follows:

  • Initialize capacity
  • Use Map to store key and value
  • After get, move node to head
  • After put, if key exist, update node value and move it to head
  • If key does not exist, check size. if size is equal or greater than capacity, remove the tail. add the new node to head. increase the size by one.


class LRUCache {
  private capacity: number;
  private map: Map<number, number>;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key: number): number {
    if (this.map.has(key)) {
      const value = this.map.get(key);
      this.map.delete(key);
      this.map.set(key, value);
      return value;
    }
    return -1;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
  }
}

Output

//Example
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // returns 1
cache.put(3, 3); // evicts key 2
console.log(cache.get(2)); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
console.log(cache.get(1)); // returns -1 (not found)
console.log(cache.get(3)); // returns 3
console.log(cache.get(4)); // returns 4

إرسال تعليق

Please do not post any spam link in the comment box😊

أحدث أقدم

Blog ads

CodeGuru