LRU 알고리즘을 LinkedHashMap을 이용해 구현하기

서론

지난 게시글(LRU 알고리즘 파헤치기)로 LRU 알고리즘에 대해 OS와 HW 관점에서 알아봤습니다. 이번에는 Java를 이용해 이것을 구현하려면 어떻게 해야 할지 알아보고자 합니다. Java의 `LinkedHashMap`을 이용하면 편리하게 구현할 수 있습니다.

 

LinkedHashMap?

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

공식 문서에 따르면 `doubly linked list`를 이용해서 데이터의 삽입 순서를 보장해주는 HashMap이라고 합니다.

 

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

한편, 특별한 생성자를 제공하는데요. `Access-order`를 보장하는 기능을 제공하는데, 이것이 LRU 캐싱 알고리즘의 핵심 원리입니다. 해당 생성자는 다음과 같은 형태입니다.

LinkedHashMap​(int initialCapacity, float loadFactor, boolean accessOrder)

• accessOrder: true for access-order, false for insertion-order

 

구현

/**
 * @Author : yion
 * @Date : 2017. 6. 1.
 * @Description : 가장 오랫동안 사용되지 않은 엔트리(호출되지 않는)를 메모리의 후방에 위치하게 하여 메모리에서 삭제 하는 캐싱 알고리즘
 * LRU (최근사용우선) 와 비슷한 알고리즘으로 LFU(Least Frequently Used : 참조 횟수 기준) 이 있다.
 */
public class LRUCache<K, V> {

	private static final float hashTableLoadFactor = 0.75f;

	private LinkedHashMap<K, V> map;
	private int cacheSize;

	public LRUCache(int cacheSize) {
		this.cacheSize = cacheSize;

		int capacity = (int) Math.ceil(cacheSize / hashTableLoadFactor) + 1;

		map = new LinkedHashMap<K, V>(capacity, hashTableLoadFactor, true) {
			private static final long serialVersionUID = 1;
			@Override protected boolean removeEldestEntry (Map.Entry<K, V> eldest) {
				return size() > LRUCache.this.cacheSize;
			}
		};
	}

	public synchronized V get(K key) {
		return map.get(key);
	}

	public synchronized void put(K key, V value) {
		map.put(key, value);
	}

	public synchronized void clear() {
		map.clear();
	}

	public synchronized int usedEntries() {
		return map.size();
	}

	public synchronized Collection<Map.Entry<K,V>> getAll() {
		return new ArrayList<>(map.entrySet());
	}
}

• `cacheSize` : LRU Cache의 최대 크기를 설정합니다. 이 크기를 초과하면 항목을 제거합니다.
• `hashTableLoadFactor` : capacity의 몇 퍼센트가 찼을 때 용량을 늘리는 지를 정의합니다.
• `capacity` : 실제 초기 용량을 계산합니다. 충분한 초기 용량과 함께 해시 충돌을 최소화합니다.
• `removeEldestEntry`는 Victim으로 선정된 item을 제거하기 위해서 오버라이드 되었습니다. 이 메서드는 맵에 새로운 엔트리가 추가될 때마다 호출됩니다.

 

테스트

public static void main(String[] args) {
    LRUCache<String, String> c = new LRUCache<>(3);

    c.put("1", "one");      // 1
    c.put("2", "two");      // 2 1
    c.put("3", "three");    // 3 2 1
    c.put("4", "four");     // 4 3 2

    if (c.get("2") == null) {
        throw new Error();  // 2 4 3
    }

    c.put("5", "five");     // 5 2 4
    c.put("4", "four");     // 4 5 2

    for (Map.Entry<String, String> e : c.getAll()) {
        System.out.print(e.getKey() + " ");
    }
}

출력 결과 : 2 5 4

if문을 이용해 데이터에 접근했을때의 순서도 보장한다는 사실을 확인할 수 있습니다.

 

참조

공식문서 - https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedHashMap.html
도서 - 개발자기술면접노트

코드 - https://github.com/gliderwiki/java8/blob/master/src/main/java/algorithm/lru/LRUCache.java

https://velog.io/@sweet_sumin/LinkedHashMap-%EB%82%B4%EB%B6%80-%EA%B5%AC%EC%A1%B0-%EC%82%B4%ED%8E%B4%EB%B4%A4%EC%96%B4