[algorithm] LinkedHashMap - 순서를 유지하는 HashMap

들어가며

릿코드의 LRU Cache 문제를 풀다가 이 자료구조를 알게 되었다. 처음에는 HashMap으로 직접 LRU Cache에 해당하는 알고리즘을 작성하였으나, 입력값이 커지니 Time limit exceed 가 발생했다.

이 문제의 솔루션은 LinkedHashMap 을 확장하는 것으로 별다른 로직 추가 없이 LRU Cache의 요구사항을 만족시킬 수 있었다. 이런 건 그냥 지나갈 수 없다. 간단하게라도 이 자료구조를 학습해보고 정리해본다.

 

LinkedHashMap 이란 무엇인가?

• HashMap의 모든 기능은 그대로 사용할 수 있다.
• 추가적으로, 저장된 데이터들의 순서를 유지한다.
• 순서를 유지하기 위해 이중 연결 리스트 (Doubly Linked List)를 사용한다.
• 따라서 메모리 사용량이 HashMap 보다 높다.

 

API 문서를 읽고, 순서를 보장하기 위해 필요한 부분만 따로 정리를 해 보았다.

 

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

• initialCapacity : 수용량, 최대 몇 개의 데이터를 보관할 것인지를 정의한다.
• loadFactor : 자세한 설명은 위키피디아를 참고, 기본 값은 0.75이다.
• accessOrder : 해당 값을 true로 넘기면 순서 모드를 사용한다.

 

예를 들어서 위의 릿코드 문제를 풀기 위한 코드를 아래와 같이 작성할 수 있다.

public class LRUCache extends LinkedHashMap<Integer, Integer> {

    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true); //순서 모드로 사용
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1); //값이 존재하지 않을 시, -1 반환
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    // 아래 조건을 만족하는 경우, 가장 오래된 요소를 삭제한다. 재정의하지 않으면 기본 값은 false이다.
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; //최대 수용량을 넘는 경우에 가장 오래된 요소를 삭제한다.
    }
}

느낀 점

LRU Cache 문제는 LinkedHashMap 자료구조를 알고 있었다면 바로 풀 수 있는 문제였다.

나는 몰랐기에 일일이 구현하고도 Time limit exceed 가 발생했다.

PS 문제의 유형별로 Best Case 알고리즘이 있듯이 (ex : 최소 경로 탐색 - BFS) Best Case 자료구조도 있다는 생각이 든다.

더 많은 문제와 다양한 해법을 파악해서, 어떤 문제를 봤을때 바로 Best Case 알고리즘과 자료구조를 떠올릴 수 있도록 해야겠다.

 

참고 문서

[Java] LinkedHashMap — 순서를 유지하는 해시맵

LinkedHashMap (Java Platform SE 8 )