[LeetCode] 146. LRU Cache - Class(레퍼런스 객체) + 해시맵(HashMap) + LinkedHashMap JAVA

https://leetcode.com/problems/lru-cache/

코드설명

Class(레퍼런스 객체) + 해시맵(HashMap) + LinkedHashMap 을 활용합니다.

LRU Cache는 Least Recently Used Cache를 제거하는 캐싱 정책입니다.

이를 구현할때, 기본적으로 HashMap을 사용해야한다는 점은 O(1) 안에 처리하라는 조건이 있어 알 수 있습니다.

HashMap을 사용하면서, LRU Cache를 구현하기 위해서는 Cache가 사용된 데이터들의 사용빈도를 기반으로 하여 관리하면서, 그 위치를 알아야 하기에 ArrayList를 사용해야 한다고 생각했습니다. 하지만, 이 방식은 순서는 보장하지만, 시간복잡도 O(1)안에 처리하지 못합니다. ( 그안에서 삭제될경우 안의 요소들이 이동되기 때문 ) 

그렇기에 HashMap<Integer, Node> 를 통해서 처리해야만 시간복잡도 O(1) 안에 처리할 수 있습니다.

 

이러한 구현을 LinkedHashMap에서 구현하여 자바 라이브러리 API 로 제공하는데, 해당 방식을 사용하여도 됩니다.

특이사항은, LinkedHashMap 객체를 인스턴스화할때, capacity = 용량, 0.75f는 해시테이블이 얼마나 차면 리사이징할지, true는 accessOrder, 즉 들어온 순서대로 처리할지에 대하여 입니다. 이 코드 자체가 LRU를 보장합니다. 

LinkedHashMap은 Key가 들어온 순서대로 저장하는데, 이때 true로 설정함으로써 접근순서에 따른 순서로 바꾸어줍니다.

추가로, 제거할시에는 removeEldestEntry 를 Override하여 구현함으로써 초과될시 자동으로 가장 오래전에 사용된 객체를 삭제해줍니다.

this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity; // 용량 초과 시 가장 오래된 항목 제거
        }
    };
}

코드

Node 래퍼런스 클래스를 활용하여 cache HashMap에서 가리키는 위치를 포인터시킵니다.

아래 오답코드를 보면 알 수 있듯이, 가장 문제점은 위치를 갱신시키는 방법에 대한 것 이었습니다.

Node Class를 활용하고, Dummy Class인 Oldest와 Latest를 통해 위치를 갱신시키는 로직이 사라지고 주소값 기반으로 처리할 수 있게 됩니다. 처음에 드는 생각은, put 과정에서 기존의 Node를 그대로 사용하면 더 좋을 것 이라고 생각했지만, Cache의 Key값이 바뀔 수 있으므로 그 과정에서 새로 해당 cache값의 value값을 변경시켜주어야 합니다. 

class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private Node oldest;
    private Node latest;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.oldest
         = new Node(-1, -1);
        this.latest = new Node(-1, -1);
        this.oldest.next = this.latest;
        this.latest.prev = this.oldest;
    }
    
    public int get(int key) {
        if(cache.containsKey(key)){
            Node node = cache.get(key);
            remove(node);
            insert(node);
            return node.val;
        }
        return -1;
    }
 
    private void remove(Node node){
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
    }
 
    private void insert(Node node){
        Node prev = latest.prev;
        Node next = latest;
        prev.next = next.prev = node;
        node.next = next;
        node.prev = prev;
    }
 
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            remove(cache.get(key));
        }
        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        insert(newNode);
        if(cache.size() > capacity){
            Node lru = oldest.next;
            remove(lru);
            cache.remove(lru.key);
        }
    }
}
 
class Node{
    int key;
    int val;
    Node prev;
    Node next;
    public Node(int key, int val){
        this.key = key;
        this.val = val;
        this.prev = prev;
        this.next = null;
    }
}
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

 

위의 구현이 제공되는 LinkedHashMap 라이브러리입니다.

import java.util.*;
 
class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity; // 용량 초과 시 가장 오래된 항목 제거
            }
        };
    }
 
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
 
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

 

처음에 시도한 오답코드입니다.

틀린 이유는, Cache가 꽉 찬 상태에서 새로운 <key, value>가 들어왔을 때 LRU Cache 정책에 의해 맨 앞의 값을 제거하거나 맨 뒤의 값을 제거해야하는데, 이렇게 유지하기 위해서는 다른 값들의 Index들이 PUT, GET 하는 과정에서 모두 이동시켜줘야 되면서 시간복잡도가 평균 O(1) 이 되도록 할 수 없기 때문입니다.

즉, 코드의 구조자체가 시간복잡도의 조건을 통과하지 못합니다.

class LRUCache {
    HashMap<Integer, Integer> hashmap;
    ArrayList<int[]> arr;
    int capacity = 0;
    public LRUCache(int capacity) {
        hashmap = new HashMap<Integer, Integer>();
        arr = new ArrayList<int[]>();
        this.capacity = capacity;
    }
    
    //가장 최근에 사용된걸 맨뒤로 바꿔주자.
    public int get(int key) {
        int arrIdx = hashmap.get(key);
        return arr.get(hashmap.get(key));
    }
    
    public void put(int key, int value) {
        if(capacity <= 0){
            //swap first and last
            int[] lastArr = arr.get(arr.size() - 1);
            int lastKey = lastArr[0];
            int lastValue = lastArr[1];
 
            int[] firstArr = arr.get(0);
            int firstKey = fisrtArr[0];
            int firstValue = firstArr[1];
 
            hashmap.put(lastKey, 0);
            arr.get(0) = lastArr;
            hashmap.remove(firstKey);
            capacity++;
        }
        hashmap.put(key, arr.size());
        arr.add(new int[] {key, value});
        capacity -= 1;
    }
}
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */