Java를 이용하여 LRU(Least Recently Used) 알고리즘을 구현해보자

구현의도

LeetCode에서 Medium문제를 고르다가 일반적인 알고리즘의 문제는 아니어 보이는 문제를 발견하였습니다.

LeedCode_146_LRUCache

LRU Algorithm은 분명 운영체제에서 페이징 교체 방식으로 알고있는데 이걸 코테 문제로 보니 상당히 어지러워보였지만 흥미로워보여서 기존에 지식을 다시 재정비하면서 구현하기 시작하였습니다.

Cache Memory 와 캐싱 (컴퓨터 구조적 관점에서)

페이징 교체 Cache Algorithm (LRU, LFU, FIFO)

페이징 교체 알고리즘은 여러 알고리즘이 있지만 OPT,LFU, LRU, FIFO 정도만 알고있었고 그 중 문제에서 제공하는 예제와 함께 LRU 알고리즘을 그림으로 표현해보았습니다.

LRU Cache를 구현하기위해 고려해야하는 사항들

문제에서 제공하는 조건들이 LRU Cache를 구현할 때 가장 중요한 것들인 것 같아
정리해보았습니다.

• put()과 get() 모두 사용한 숫자로 처리됩니다.
• put()과 get()에 따른 순서가 지속적으로 바뀝니다.
• O(1)의 시간복잡도를 유지해야합니다.
• input key - value
• put()에 과정에서 순서를 보장해야합니다.

문제 접근

위에 1번 2번 조건들을 살폈을 때 떠오르는 자료구조는

• LinkedList와 DoublyLinkedList.
  LinkedList는 Java에서 구현체로 존재하지만
  DoublyLinkedList는 없어서 Node에 head, tail을 만들어야하는 다소 복잡한 절차가 따릅니다.(Java에서 LinkedList는 이미 DoublyLinkdedList라고 알고있긴한데..)

3번과 4번 조건들을 살폈을 때 가장 적절한 자료구조는 Java에서 존재하는

• HashMap
  하지만 HashMap은 5번 조건에 위배됩니다. (put의 순서가 보장되지 않기때문에)
  

  

  다른 언어 C, C++, Python이랑 다르게 이러한 캐싱알고리즘을 위해서 Java에서는 LinkedHashMap이라는 자료구조를 제공하고있습니다.

LinkedHashMap

위와같이 key - value형식을 head tail들과 함께 엮어 양방향 연결리스트처럼 구현한 구현체.

위와같이 LinkedHashMap의 생성자들은 기본생성자를 제외하고 4가지로 이루어지는데

요구사항에 알맞는(5번)에 필요한 생성자는 InitialCapacity와 순서를 보장하는 accessOrder만 있는 생성자이지만 없습니다.

그래서 불가피하게 LinkedHashMap(int Capacity, float loadFactor, boolean accessOrder) 생성자를 사용해야합니다.

loadFactor란?
HashMap의 부하율.
버킷이 얼마나 채워졌을 때 크기를 늘릴지 결정하는 값.
낮은 부하율(예: 0.5): 더 많은 메모리를 사용하지만 충돌을 줄여 성능 향상.
높은 부하율(예: 1.0): 메모리를 절약하지만 충돌 가능성이 높아져 성능 저하.

왜 0.75f? (stackOverFlow)

Ideally, under random hashCodes, the frequency of nodes in binsfollows a Poisson distribution with a parameter of
0.5on average for the default resizing threshold of 0.75f

이상적으로, 무작위 해시 코드에서 빈의 노드 빈도는 평균적으로 기본 크기 조정 임계값 0.75f에 대해 매개변수가 0.5인 포아송 분포를 따릅니다.

요약하면,
0.75f일때 가장 최적화되어있다.

문제 해결

import java.util.*;

class LRUCache {

    public LinkedHashMap<Integer, Integer> linkedHashMap;
    public int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        //accessOrder = true -> 접근할떄 지속적 순서 보장. 
        this.linkedHashMap = new LinkedHashMap<>(capacity, 0.75f, true);
    }

    public int get(int key) {
        return linkedHashMap.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        linkedHashMap.put(key, value);
        
        if (linkedHashMap.size() > capacity) {
            int leastUsedKey = linkedHashMap.keySet().iterator().next();
            linkedHashMap.remove(leastUsedKey);
        }
    }
}

put과정에서 iterator을 사용해서 Capacity가 넘어가면 첫번째오는 int를 삭제하는 로직으로 구현하였지만

Java Docs를 확인해보면 실제로 메모리 캐싱을 위해서 지원하는 메서드를 사용한다면 더욱 더 가독성있는 코드가 되지않을까 싶습니다.