[cache] LRU 알고리즘 with LinkedHashMap

💡 Cache 알고리즘 중 가장 유명하다고 하는 LRU 알고리즘을 LinkedHashMap을 활용하여 공부해보았다.

LRU (Least Recently Used)

LRU 알고리즘은 운영체제의 페이지 교체 알고리즘 중 하나이다. Cache 알고리즘 중 가장 유명한 알고리즘 이기도 하다.
LRU 알고리즘은 가장 오랫동안 참조되지 않은 항목을 교체 하는 알고리즘이다.

LinkedHashMap 으로 구현하기

LinkedHashMap 의 다음 생성자를 활용하였다.

accessOrder 속성

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

accessOrder 값을 true 로 생성하면 내부적으로 key에 접근할 때 마다 afterNodeAccess() 메소드를 실행한다.
afterNodeAccess()메소드는 최근에 접근한 노드를 가장 마지막 노드로 위치시킨다.

removeEldestEntry() 메소드

가장 오래된 값을 대체할 때 사용한다.
기본 값은 false지만 LRU 를 구현할 때 지정된 사이즈를 넘어가면 오래된 값 부터 지워지도록 할 것이기 때문에 다음과 같이 오버라이딩 한다.

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > size;
}

LRU Test

다음은 size를 10으로 지정하고 1부터 10까지 순서대로 key와 value를 초기화 시킨 뒤 다음의 작업을 한 결과다.

• 3은 get()으로 접근
• 5, 2는 put()으로 값 업데이트
• 11은 put()으로 값 입력

====[LRU test]====
key-4=value-4
key-6=value-6
key-7=value-7
key-8=value-8
key-9=value-9
key-10=value-10
key-3=value-3
key-5=value-5-update
key-11=value-11-insert
key-2=value-2-update

가장 최근에 접근한 2,3,5,11 key가 뒤 순서로 정렬되고 size가 10이기 때문에 맨 앞의 key로 있었을 key-1이 먼저 삭제된 것을 알 수 있다.