146. LRU 캐 시 시스템 HashMap + 양 방향 링크 실현 O (1) 복잡 도

당신 이 파악 한 데이터 구 조 를 활용 하여 LRU (최근 최소 사용) 캐 시 체 제 를 설계 하고 실현 합 니 다.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.진급: 당신 은 O (1) 시간 복잡 도 내 에 이 두 가지 조작 을 완성 할 수 있 습 니까?예제: LRUCache cache = new LRUCache (2 / * 캐 시 용량 * /);cache.put(1, 1); cache.put(2, 2); cache.get(1); // 1 cache. put (3, 3); /이 동작 은 키 2 를 cache. get (2) 로 폐기 합 니 다. /반환 - 1 (찾 을 수 없 음) cache. put (4, 4); /이 동작 은 키 1 을 cache. get (1) 로 폐기 합 니 다. /반환 - 1 (찾 을 수 없 음) cache. get (3); /3 cache. get (4); /돌아오다
사고방식: HashMap + 양 방향 체인 테이블 의 사고방식 을 이용 하 는 것 은 사실 매우 간단 하 다. 매번 put / get 조작 이 이미 있 는 노드 를 방문 한 후에 노드 를 양 방향 체인 테이블 의 끝으로 이동한다.put 에 없 는 결점 을 넣 으 면 바로 끝부분 에 삽입 하면 됩 니 다.put 작업 을 할 때 cache 공간 이 부족 하면 첫 번 째 노드 를 제거 합 니 다 (LRU 가 최근 에 가장 적 게 사용 한 노드).
자바 에는 링크 드 하 쉬 맵 이 있 습 니 다. 우 리 는 이 종 류 를 계승 하면 위의 방법 을 쉽게 실현 할 수 있 습 니 다.

 class LRUCache{
 		class Node{
            int key;
            int val;
            Node pre;
            Node next;
        }
        private int idx; //  cache      
        private int capacity; //cache   
        private HashMap<Integer, Node> cache;
        private Node head; //  O(1)     
        private Node tail; //  O(1)       
        public LRUCache(int capacity) {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
            idx = 0;
            this.capacity = capacity;
            cache = new HashMap<>(capacity); //          rehash   
        }
        private void remove(Node node){ //      
            Node tempPre = node.pre;
            Node tempNext = node.next;
            tempPre.next = tempNext;
            tempNext.pre = tempPre;
        }
        private void setLast(Node node){ //       
            Node tempTailPre = tail.pre;
            tempTailPre.next = node;
            node.pre = tempTailPre;
            node.next = tail;
            tail.pre = node;
        }
        private void removeHead(){ //     
            Node temp = head.next;
            head.next = temp.next;
            temp.next.pre = head;
            cache.remove(temp.key);
        }
        public int get(int key) {
            if(cache.containsKey(key)){
                Node cur = cache.get(key);
                if(tail.pre == cur){
                    return cur.val;
                }
                remove(cur);
                setLast(cur);
                return cur.val;
            }
            return -1;
        }
        public void put(int key, int value) {
            Node cur = cache.get(key);
            if(cur == null){
                Node newNode = new Node();
                newNode.key = key;
                newNode.val = value;
                if(idx >= capacity){ //      cache    
                    removeHead();
                }
                ++idx;
                setLast(newNode);
                cache.put(key, newNode); 
            }else {
                cur.val = value;
                remove(cur);
                setLast(cur);
            }
        }
    }

LinkedHashMap 실현

class LRUCache{
        private LRU cache;
        public LRUCache(int capacity) {
            this.cache = new LRU(capacity);
        }
        public int get(int key) {
            if (cache.containsKey(key)) {
                return cache.get(key);
            }
            return -1;
        }
        public void put(int key, int value) {
            cache.put(key, value);
        }
        class LRU extends LinkedHashMap<Integer, Integer> {
            int capacity;
            public LRU(int capacity) {
                //       ordering mode，        (put、get)         
                super(capacity, 0.75f, true);
                this.capacity = capacity;
            }
            //removeEldestEntry             ，                
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> entry) {
                return this.size() > capacity;
            }
        }
    }

링크 드 하 쉬 맵 이 봉 인 된 방법 으로 LRU 를 실현 하 는 것 이 더욱 간편 해 보인다.