알고리즘 문제를 풀다 LinkedHashMap 에 대해 확인하던 중, LRU cache 를 구현하는데 적합한 자료구조라는 것을 알게되었다. 아래 내용은 jdk 8 공식 홈페이지의 LinkedHashMap 일부 내용이다.
This kind of map is well-suited to building LRU caches.
LinkedHashMap 의 내부 로직이 어떻게 되길래 LRU cache 구현에 적합한지 궁금해서 찾아보게 되었다. 참고로 LinkedHashMap 은 jdk 1.4 에서 최초 추가되었다.
공식 홈페이지의 내용을 계속 읽어보니 removeEldestEntry 메서드를 통해 새로운 데이터가 들어왔을 때 제거 정책을 어떻게 할지 정할 수 있다고 한다.
The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
자세한 로직을 확인하기 위해 최근 가장 많이 사용하는 버전인 jdk 11 내부를 분석해봤다.
LinkedHashMap 은 HashMap 을 상속하고 Map 을 구현한다. 따라서 내부 데이터를 저장하는 구조와 기존적인 데이터 저장, 삭제 같은 메서드는 HashMap 과 동일하다. (LinkedHashMap 는 그외에 링크드 리스트 구조의 자료 형태를 유지하기 위한 변수와 메서드들이 존재한다.)
따라서 LinkedHashMap 에서 put 을 하게되면 HashMap 내부 putVal 메서드를 통해 데이터가 적재된다. 이때 putVal 메서드 내부 마지막에서 afterNodeInsertion 메서드를 호출한다. 이때 evict 이라는 변수를 매개변수로 전달하게 되는데 일반적으로 true 상태가 디폴트 값이다.
afterNodeInsertion 메서드는 LinkedHashMap 에서 다음과 같이 구현되어 있다.
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}removeEldestEntry 메서드의 기준에 따라 첫번째 데이터를 삭제하게 된다. removeEldestEntry는 오버라이딩하지 않으면 기본적으로 false 를 리턴하게 하여 기존의 데이터를 삭제하지 않도록 설계되어 있다.
따라서 LRU cache 로서 사용하고 싶다면 다음과 같이 조건을 주어서 삭제 정책을 적용해주어야 한다.
class ExpiringCache {
private Map<String,Entry> map;
private int MAX_ENTRIES = 200;
...
ExpiringCache(long millisUntilExpiration) {
this.millisUntilExpiration = millisUntilExpiration;
map = new LinkedHashMap<>() {
protected boolean removeEldestEntry(Map.Entry<String,Entry> eldest) {
return size() > MAX_ENTRIES;
}
};
}
}자세한 이해를 돕기위해 실제 오픈소스에서 사용중인 예시를 가져왔다. 위 예시는 현재 LinkedHashMap 내부 데이터 크기가 MAX_ENTRIES 보다 크면 가장 첫번째 데이터를 삭제하는 예시로 java.io 의 ExpiringCacha 클래스이다.
그런데 아직 LinkedHashMap 가 LRU cache 로서 적합한지 확실하게 알 수 없다 왜냐면 가장 마지막으로 사용된 데이터가 삭제되는지 확인이 필요하기 때문이다. afterNodeInsertion 에서 맵의 첫번째 데이터를 삭제하는 것을 확인하였는데 첫번째 데이터는 어떻게 정해지는지 확인해보겠다.
putVal 메서드를 사용하여 데이터를 적재 할 때 신규 key로 데이터를 만드는 상황과 신규 key와 기존 key가 충돌나는 상황이 있다.
- 신규 key로 데이터를 만드는 상황
먼저 데이터가 기존에 없으면 newNode 메서드로 생성을 하는데 이때 LinkedHashMap 에서는 linkNodeLast 라는 메서드를 추가로 호출하여 만들어진 데이터를 tail 값을 통해 리스트 가장 맨 끝으로 연결한다.
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
- 신규 key와 기존 key 충돌 상황
데이터 충돌이 발생하였을 때는 afterNodeAccess 메서드를 추가로 호출한다. 해당 메서드는 매개변수로 들어온 Node 데이터를 리스트 가장 맨 끝으로 연결하고 있다.
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}이런 동작에 따라 LinkedHashMap 자료구조 내부 리스트에서 가장 앞 데이터는 가장 오래된 데이터임을 확인할 수 있다.
결과적으로 put 을 했을 때 캐시가 허용 범위를 가득차면 가장 오래된 데이터를 삭제하고 기존 데이터에 대해 갱신이 되었을 때 최신 데이터로 위치를 조정하고 있어 LRU(Least Recently Used) cache 를 구현하는데 적합한 자료구조임을 확인할 수 있다.
참고
- https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html