java 1.4 Collections API에 새롭게 첨가된 java.util.LinkedHashMap 클래스는 HashMap처럼 해쉬테이블에 기반을 둔 Map 클래스 입니다. LinkedHashMap이 다른 점은 맵 엔트리에서 실행되는 링크된 리스트를 관리할 수 있고 또한 그 엔트리에 대해서 예측할 수 있는 반복 작업을 수행할 수 있다는 것이다. 대부분 이 순서는 맵에 엔트리가 추가된 순서대로 되고 가끔씩 아주 유용한 특징으로 사용할 수 있는 상황도 있습니다. 

LinkedHashMap은 생성자의 세 번째 인자로 true 값을 넘겨줌으로써 가장 최근에 접근(즉 조회되거나 설정된) 순서에서 가장 오래 전에 접근된 순서로 엔트리 순서를 설정할 수 있다.

그리고, LinkedHashMap의 removeEldestEntry()를 새로운 Entry가 추가될 때 마다 호출을 하게되면, 이 메소드가 true를 반환하면 맵에서 '가장 오래된' Entry, 즉 가장 오래 전에 입력되거나 사용된 것은 자동적으로 삭제된다. removeEldestEntry()의 기본값으로 항상 false를 반환하지만 맵이 정해진 어떤 최고 크기에 다다르면 true 값을 반환하도록 오버라이드 할 수 있다. 이와 같이 하면 LRU(least-recently-used) 캐시를 만들 수 있는 것입니다.

public class LRUCache extends java.util.LinkedHashMap {
    public LRUCache(int maxsize) {
        super(maxsize*4/3 + 1, 0.75f, true);
        this.maxsize = maxsize;
    }
    protected int maxsize;
    protected boolean removeEldestEntry() {
        return size() > maxsize;
    }
}