스냅 백 (LeetCode) - 146 LRU 캐 시 메커니즘

이 문제 에서 고찰 한 LRU 캐 시 메커니즘, HashMap 과 링크
제목 설명
당신 이 파악 한 데이터 구 조 를 활용 하여 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); /돌아오다
제목 사고
우선 LRU 알고리즘 의 원 리 를 알 아야 한다.LRU 알고리즘 은 한 데이터 가 오랫동안 접근 하지 않 았 기 때문에 이 데 이 터 는 앞으로 도 거의 접근 하지 않 을 것 이다.오랫동안 접근 하지 않 은 데이터 에 대해 캐 시 공간 이 부족 하면 오랫동안 사용 하지 않 았 던 데 이 터 를 지 웁 니 다.
그러면 어떻게 이런 알고리즘 을 실현 합 니까?우 리 는 모든 데이터 에 시간 스탬프 를 표시 하고 최근 에 사용 한 시간 을 표시 한 다음 에 시간 스탬프 를 계속 업데이트 할 수 있 습 니 다. 캐 시가 공간 이 없 을 때 현재 가장 오래된 시간 스탬프 를 삭제 할 수 있 습 니 다.이런 방법 은 배열, 링크 로 실현 할 수 있 고 시간 복잡 도 는 보통 O (n) 이다.
또는 시간 스탬프 를 표시 하지 않 아 도 됩 니 다. 저 희 는 데이터 의 사용 시간 에 따라 데 이 터 를 정렬 할 수 있 습 니 다. 최근 에 사용 한 것 은 앞 에 있 고 오랫동안 사용 하지 않 은 것 은 뒤에 있 습 니 다.데 이 터 를 삭제 하려 면 뒤에서 부터 삭제 합 니 다.데 이 터 를 찾 을 때 HashMap 을 사용 할 수 있 습 니 다.이렇게 하면 시간 복잡 도 를 O (1) 로 간소화 할 수 있다.
이렇게 많은 말 을 했 으 니, 우 리 는 세부 사항 을 정리 하고, 산법 의 구체 적 인 실현 을 말 해 보 자.
1. 먼저 우 리 는 양 방향 링크 를 유지 해 야 한다. 이 링크 에서 우 리 는 링크 의 데 이 터 를 이렇게 배열 해 야 한다. 가 까 울 수록 사용 하 는 데 이 터 는 앞 에 있 고 오래 사용 하지 않 은 데 이 터 는 뒤에 있어 야 한다.그 밖 에 링크 의 모든 데 이 터 는 HashMap 에 천천히 존재 합 니 다.
2. 우리 가 데 이 터 를 삽입 할 때 먼저 HashMap 에 이 데이터 가 있 는 지 찾 습 니까?
2.1 만약 에 이 데이터 가 없다 면 우 리 는 현재 HashMap 에 남 은 공간 이 있 는 지 판단 해 야 한다.남 은 공간 이 없 으 면 양 방향 링크 의 마지막 데 이 터 를 삭제 해 야 합 니 다 (HashMap 에서 도 이 데 이 터 를 삭제 하고 삭제 할 때 빈 포인터 등 이상 상황 에 주의 하 십시오).그리고 삽입 할 데 이 터 를 양 방향 링크 의 머리 에 넣 습 니 다.
2.2 이 데이터 가 있 으 면 우 리 는 먼저 이 데 이 터 를 전구 와 백 드라이브 와 끊 어야 합 니 다. (빈 포인터 이상 이 발생 할 수 있 음 을 주의 하 십시오) 그리고 이 데 이 터 를 끝 점 에 삽입 해 야 합 니 다.
3. 우리 가 데 이 터 를 가 져 와 야 할 때 HashMap 에 이 데이터 가 있 는 지 찾 아 보 세 요.
3.1 이 데이터 가 있 으 면 우 리 는 먼저 이 데 이 터 를 전구 와 백 드라이브 와 끊 어야 한다. (빈 포인터 이상 이 발생 할 수 있 음 을 주의 하 라) 그리고 이 데 이 터 를 끝 점 에 삽입 해 야 한다.
3.2 이 데이터 가 없 으 면 - 1 을 되 돌려 줍 니 다.
코드

class LRUCache {
    /**
    *       
    * 1.        ，           
    * 2.     ，    cache       ？    ，          ？      ，           。              
    * 3.  key       ，  cache    key     ？   ，            ，    ：：    ，  -1。
    */
    private int capacity;
    private LinkNode first;
    private LinkNode last;
    private HashMap cache;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        cache = new HashMap(capacity);
    }
    
    public int get(int key) {
        LinkNode res=cache.get(key);
        if(res==null){
            return -1;
        }
        moveNodeToFirst(res);
        return res.val;
    }
    
    public void put(int key, int value) {
        LinkNode temp=cache.get(key);
        if(temp==null){
            if(cache.size()>=capacity){
                removeLastNode();
            }
            temp=new LinkNode();
            temp.key=key;
        }
        temp.val=value;
        moveNodeToFirst(temp);
        cache.put(key,temp);
    }
    
    private void removeLastNode(){
        LinkNode temp=last;
        last=last.pre;
        if(last!=null){
            last.next=null;
        }else{
            first=last=null;
        }
        cache.remove(temp.key);
    }
    
    private void moveNodeToFirst(LinkNode node){
        if(first==node) return;
        if(node.pre!=null){
            node.pre.next=node.next;
        }
        if(node.next!=null){
            node.next.pre=node.pre;
        }
        if(node==last){
            last=last.pre;
        }
        if(last==null){
            last=first=node;
            return;
        }
        node.next=first;
        first.pre=node;
        node.pre=null;
        first=node;
    }
}

class LinkNode{
    LinkNode pre;
    LinkNode next;
    int key;
    int val;
}