LeetCode - 146. LRU 캐 시 메커니즘

제목.
당신 이 파악 한 데이터 구 조 를 활용 하여 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); /돌아오다
문제 풀이 방향 - 양 방향 링크 + 해시 표: 양 방향 링크 와 해시 표 의 결합 을 사용 하면 O (1) 의 시간 복잡 도 에서 LRU 캐 시 체 제 를 완성 할 수 있 습 니 다.표 헤드 와 표 끝 이 있 는 더 블 링크 를 구축 하여 LRU 색인 표 로 하고 HashMap 을 데이터 시트 로 하여 모든 링크 노드 를 저장 하 며 추가 하거나 업데이트 하 는 노드 를 링크 헤드 에 두 고 HashMap 의 개수 가 용량 상한 선 에 도달 하면 링크 의 마지막 노드 를 삭제 합 니 다.데 이 터 를 가 져 올 때 HashMap 에서 대응 하 는 key 값 value 를 직접 가 져 오 면 됩 니 다.
문제 풀이 사고방식 - LinkedHashMap 사용: LinkedHashMap 은 Map 인터페이스의 해시 테이블 과 양 방향 체인 테이블 의 결합 으로 LRU 캐 시 메커니즘 을 실현 하기에 특히 적합 하 다.링크 드 HashMap 에 참조 가 있 는 구조 함수 가 있 습 니 다:

public LinkedHashMap(int initialCapacity,  float loadFactor,  boolean accessOrder) {  
    super(initialCapacity, loadFactor);  
    this.accessOrder = accessOrder;  
}

그 중:

initial Capacity 는 HashMap 의 통 수량 (기본 값 은 16 개) 입 니 다.

loadFactor 는 적재 인자 로 HashMap 의 통 이 가득 찼 는 지 판단 하 는 데 사 용 됩 니 다. loadFactor 의 기본 값 은 0.75f 이 고 적재 인 자 를 계산 하 는 공식 은 HashMap 에 존재 하 는 KV 키 수량 / capacity 입 니 다.원소 개수 가 16loadFactor 즉 160.75 = 12 를 초과 하면 HashMap 은 먼저 2 배 에서 32 로 확대 되 고 이 어 64 등 까지 확 대 될 수 있다.

accessOrder 는 정렬 모드, boolean 형 을 정 의 했 습 니 다. 만약 에 양 방향 링크 의 정렬 이 접근 순서 가 적 고 많 으 면 true 입 니 다.삽입 순서 로 정렬 하면 false, 즉 기본 값 입 니 다.

LinkedHashMap 은 removeEldestEntry (Map. Entry eldest) 방법 도 제공 합 니 다. 이 방법 은 새로운 요 소 를 추가 할 때마다 가장 오래된 요 소 를 제거 할 수 있 습 니 다.방법 은 기본 값 을 false 로 되 돌려 줍 니 다. 오래된 요 소 를 제거 하지 않 습 니 다.반환 값 이 true 일 때 제거 기능 을 실현 할 수 있 습 니 다.방법 은 다음 과 같다.

protected boolean removeEldestEntry(Map.Entry eldest) {  
       return false;  
} 

따라서 LRU 캐 시 체 제 를 실현 하려 면 인삼 이 있 는 링크 드 HashMap 을 새로 만 들 고 Override 함수 removeEldestEntry 를 사용 하여 map. size > capacity 를 되 돌려 줍 니 다. 즉, 현재 map 의 용량 이 상한 선 을 설정 할 때 가장 오래된 요소 제거 기능 을 실현 합 니 다.자바 문제 풀이 에 서 는 두 가지 코드 구현 방식 을 제공 합 니 다. 하 나 는 클 라 스 를 새로 만 드 는 것 이 고, 또 하 나 는 정례 화 대상 일 때 override 입 니 다.
자바 문제 풀이 - 양 방향 링크 + 해시 표

import java.util.HashMap;
import java.util.Map;
class LRUCache {
//        
    class Node{
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private Node first;
    private Node last;

    private Map map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node node = map.get(key);
        if(node==null) return -1;
        movetoHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if(node==null){
            node = new Node(key, value);
            //     map    capacity 
            //            
            if(map.size()==this.capacity)
                removeLast();
            addtoHead(node);
            map.put(key, node);
        }else{
            node.value = value;
            movetoHead(node);
        }
    }
    
    //              
    public void movetoHead(Node node){
        if(node==first)
            return;
        else if(node==last){
            last.pre.next = null;
            last = last.pre;
        }else{
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.pre = first.pre;
        node.next = first;
        first.pre = node;
        first = node;
    }
    
    //            
    public void removeLast(){
        map.remove(last.key);
        Node prenode = last.pre;
        if(prenode!=null)
            prenode.next = null;
        last = prenode;
    }
    
    //             
    public void addtoHead(Node node){
        if(map.isEmpty()){
            first = node;
            last = node;
        }else{
            node.next = first;
            first.pre = node;
            first = node;
        }
    }
}

/**
 * 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 - 1 사용

import java.util.LinkedHashMap;
import java.util.Map.Entry;

class LRULinkedHashMap extends LinkedHashMap{
	//     
    private int capacity;
    //      
    public LRULinkedHashMap(int capacity){
        // accessOrder  true，    LRU  ,                      
    		// 0.75 LinkedHashMap        
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

	//      size  capacity ，  ture，         
	// macos idea ，override    command+o，           
    @Override
	protected boolean removeEldestEntry(Entry eldest) {
		return this.size() > this.capacity;
	}
}

class LRUCache {
    private LRULinkedHashMap LRUMap; //        

    public LRUCache(int capacity) {
        this.LRUMap = new LRULinkedHashMap(capacity);
    }

    public int get(int key) {
    		Integer value = LRUMap.get(key);
    		if(value==null) return -1;
    		return value;
    }

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

자바 문제 풀이 - LinkedHashMap - 2 사용

import java.util.LinkedHashMap;
import java.util.Map.Entry;
class LRUCache {

    private LinkedHashMap map;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap(capacity, 0.75f, true){
            @Override
            protected boolean removeEldestEntry(Entry eldest) {
                return this.size()> capacity;
            }
        };
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if(value==null) return -1;
        return value;
    }

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