LinkedHashmap LRU Caching

출처 - http://allpeopleparty.blogspot.com/2011/01/linkedhashmap-lru-caching.html

 

LinkedHashmap LRU Caching

LinkedHashMap의 생성자 중 LinkedHashMap(int capacity, float loadFactor, boolean accessOrder)가 있다.
capacity는 생성할때 map의 크기를 얼마로 할 것인가가 되고
loadFactor는 capacity의 몇 %가 차게되면 용량을 늘려야 할것인가
마지막 불리언 값은 정렬을 삽입 순서(false)냐 접근 순서(true)냐에 대한 인자이다.

그리고 맵에 put이 호출되면 엔트리를 생성해서 addEntry하게 되고
LinkedHashMap의 addEntry는 마지막에 removeEldestEntry를 호출하고 이 리턴이 true이면 정렬 순서의 첫 값을 삭제한다.

LRU 방식으로 특정한 크기의 자료를 유지하고 싶을때 이를 이용하면 된다.

import java.util.LinkedHashMap;
import java.util.Map;



public class LRUCache<K, V> extends LinkedHashMap<K, V>
{
    private static final long serialVersionUID = 734283243247234L;
    private final int         maxSize_;



    public LRUCache(final int maxSize)
    {
        super((maxSize + 1) * 4 / 3 + 1, .75f, true); // <-- 0.75의 load factor가 매직 넘버처럼 쓰인다.
        this.maxSize_ = maxSize + 1;
    }



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

주의해야 할 점은 capacity의 값이다. capacity의 75%가 차게 되면 capacity의 2배 증가와 re-hashing이 발생한다. max 값으로 크기가 고정 될 것이므로 굳이 용량 증가나 re-hashing을 일으킬 필요가 없으므로
용량을 max값의 4/3 크기로 한다.
또 입력받은 maxSize에 1을 더한 값으로 임계치를 정한 것은 LinkedHashMap에서 size >= threshold 조건에 걸릴때 용량 resize를 하기 때문에 입력 받은 max에 1을 더한 값과 비교하도록 한 것이다.