<알고리즘> 3. LRU 캐시 JAVA

가. 무엇인가? 

 a. 캐시 알고리즘

  -  데이터를 빠르게 가져오기도 하고 DB 부하를 줄이기 위해 캐시를 많이 사용한다.

  -  하지만 캐시에도 용량이 있기 때문에 지워주면서 사용해야한다.

  -  이런 캐시를 관리하는 여러 알고리즘이 존재한다.

 

 b. LRU

  -  Least Recently Used, 최근까지 적게 hit된 캐시데이터를 지우는 방법이다

 

나.  구현

 a. LinkedHashMap을 활용

  -  LinkedHashMap에는 두가지 정렬 모드가 있다. ( ordering mode, insertion-order mode)

        => 들어온 순서를 그대로 가져가는 모드, access로 가져가는 모드

  -  access 모드를 이용해 쉽게 LRU를 구현할 수 있다.

public static void main(String[] args) {
        Cache<String,Integer> cache = new Cache<>(3);
        cache.put("b",0);
        cache.put("a",0);
        cache.put("c",0);
        System.out.println(cache.keySet());
        cache.put("a",0); 
        System.out.println(cache.keySet());
        cache.put("d",0);
        System.out.println(cache.keySet());
        cache.put("e",0);
        System.out.println(cache.keySet());
        
        String data = "a";
        if (cache.containsKey(data)) {
           // hit
        } else {
           // miss 
        }
        cache.put(data, 0);
}
class Cache<String, Integer> extends LinkedHashMap<String, Integer>{
    int capacity = 0;

    public Cache(int capacity) {
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        // eldest 가장 오랫동안 안쓴 데이터
        return size() > capacity;
    }
}

// 출력 
[b, a, c]
[b, c, a]
[c, a, d]
[a, d, e]