소개

LRU는 가장 최근에 사용됨을 나타냅니다. LRU 캐시는 캐시가 용량에 도달하면 가장 최근에 사용된 항목이 제거되는 캐시 유형입니다.

• LRU 캐시를 사용하는 주된 이유는 데이터 액세스 성능을 향상시키기 위한 것입니다. 일반적으로 캐시에서 데이터에 액세스하는 것이 주 메모리나 원격 서버에서 데이터를 검색하는 것보다 빠릅니다.
• 가장 최근에 사용한 데이터를 캐시에 저장함으로써 캐시 적중 가능성이 높아지고, 결과적으로 데이터 검색 속도가 향상됩니다.

참고:

• 맵 데이터 구조는 해시 테이블의 동작을 모방하는 데 사용됩니다. 이를 통해 효율적인 조회, 삽입 및 삭제 작업이 가능합니다.
• 요소 간 이동이 용이하도록 이중 연결 목록이 구현되었습니다. 이는 양방향(앞으로 및 뒤로)으로 탐색하고 일정한 시간 동안 삽입 및 삭제를 수행하는 기능을 제공합니다.
• 이 두 가지 데이터 구조를 결합하면 해시 테이블과 이중 연결 목록의 장점을 모두 활용하여 효율적인 작업이 가능해집니다.

다음은 JavaScript에서 LRU 캐시를 구현하는 방법에 대한 기본 예입니다.

// Why we need this LRU
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

//Least Recently used
class LRU {
    constructor() {
     this.head = this.tail = null;
     this.map = new Map();
     this.size = 0; // Why I added size, because may be in future we can say if capacity reach to the size, we will remove the tail first and then insert.
    }

    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        }

        return -1;
    }

    update(key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        } else {
            console.log('Key not found'); 
            // Here we can check for capacity if available we can call insert
            // if capacity is not available we will remove the tail and then insert.
        }
    }

    remove(node) {
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    insert(key, value) {
        const newNode = new Node(key, value);
        this.map.set(key, newNode);
        if (this.head === null) {
            this.head = this.tail = newNode;
            this.size = 1;
            return;
        }
        // We need to insert at the Begining
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head= newNode;
        this.size  ;
        return;
    }
}

const test = new LRU();
test.insert('A', 20);
test.insert('B', 10);
test.insert('C', 5);
test.insert('D', 7);

console.log(test);
console.log('------------------');
console.log('C ---> ', test.get('C'));
console.log('D ---> ', test.get('D'));

console.log('D ---> ', test.update('B', 100));

/*
LRU {
  tail:  Node {
    key: 'A',
    value: 20,
    next: null,
    prev: Node { key: 'B', value: 10, next: [Circular *1], prev: [Node] }
  },
  head:  Node {
    key: 'D',
    value: 7,
    next: Node { key: 'C', value: 5, next: [Node], prev: [Circular *2] },
    prev: null
  },
  map: Map(4) {
    'A' =>  Node {
      key: 'A',
      value: 20,
      next: null,
      prev: [Node]
    },
    'B' => Node { key: 'B', value: 10, next: [Node], prev: [Node] },
    'C' => Node { key: 'C', value: 5, next: [Node], prev: [Node] },
    'D' =>  Node {
      key: 'D',
      value: 7,
      next: [Node],
      prev: null
    }
  },
  size: 4
}
------------------
C --->  5
D --->  7
D --->  100
B --->  100
*/

우려사항이 있으면 언제든지 문의해 주세요.