어떻게 LRU 시간 복잡 도 를 O (1) 로 기반 으로 하 는 캐 시 를 실현 합 니까?

LRU: Least Recently Used 는 최근 에 가장 적 게 사용 되 며, 캐 시 용량 이 부족 할 경우 최근 에 가장 적 게 사용 한 데 이 터 를 먼저 도태 시 킵 니 다.JVM 쓰레기 수 거 처럼 살 아 있 는 대상 을 메모리 한쪽 으로 이동 한 뒤 나머지 공간 을 지 우려 고 합 니 다.
캐 시 기본 동작 은 읽 기, 쓰기, 도태 삭제 입 니 다.
읽 기 작업 시간 이 O (1) 인 것 은 바로 hash 작업 입 니 다. HashMap 색인 key 를 사용 할 수 있 습 니 다.
쓰기 작업 시간 복잡 도 는 O (1) 이 고 링크 구 조 를 사용 하 며 링크 의 한 끝 에 노드 를 삽입 하면 O (1) 작업 을 완성 할 수 있 지만 읽 기 에 맞 추기 위해 노드 를 HashMap 에 다시 넣 어야 합 니 다. put 작업 이 가장 좋 은 것 은 O (1) 이 고 최 악의 것 은 O (n) 입 니 다.
많은 어린이 신발 에 의문 이 생 겼 습 니 다. 기록 할 때 맵 을 사용 하여 put 작업 을 했 습 니 다. 왜 캐 시 는 맵 을 직접 사용 하지 않 습 니까?맞습니다. 먼저 맵 을 사용 하여 노드 데 이 터 를 저장 한 것 은 공간 으로 시간 을 바 꾸 는 것 입 니 다. 그러나 삭제 가 잘 되 지 않 습 니 다. 맵 을 사용 하여 최근 의 최소 사용 (시간, 빈도 문제 와 관련) 을 기록 하 는 방법 입 니 다.so, 링크 를 사용 하면 활성 노드 를 링크 의 한 끝 으로 이동 시 키 고 탈락 시 다른 한 끝 에서 직접 삭제 할 수 있 습 니 다.

public class LruCache<K,V> {
	/**            */
    private int capacity = 2;
    private int size = 0;
    private HashMap<K,DoubleListNode<K,V>> cache = new HashMap<>(capacity);
    private DoubleListNode<K,V> lruNode = new DoubleListNode<K, V>(null,null,null,null);
    private DoubleListNode<K,V> mruNode = new DoubleListNode<K, V>(null,null,null,null);

    public V get(K key){
        DoubleListNode<K,V> target = cache.get(key);
        if (target == null) {
            return null;
        }
        /**           */
        move2mru(target);
        return target.value;
    }

    public void put(K key,V value){
        if(cache.containsKey(key)){
            DoubleListNode<K,V> temp = cache.get(key);
            temp.value = value;
            /**           */
            move2mru(temp);
            return;
        }

		/**          */
        if(size >= capacity){
            evict4lru();
        }
        DoubleListNode<K,V> newNode = new DoubleListNode<>(mruNode,null,key,value);
        if(size == 0){
            lruNode.next = newNode;
        }
        mruNode.next = newNode;
        mruNode = newNode;
        cache.put(key,newNode);
        size++;
    }

    private void move2mru(DoubleListNode<K,V> newMru){
        DoubleListNode<K,V> pre = newMru.pre;
        DoubleListNode<K,V> next = newMru.next;
        pre.next = next;
        newMru.pre = mruNode;
        mruNode.next = newMru;
        mruNode = newMru;
    }

    private void evict4lru(){
    	cache.remove(lruNode.next.key);
        lruNode.next = lruNode.next.next;
        size--;
    }

    public String toString(){
        StringBuffer sb = new StringBuffer("lru -> ");
        DoubleListNode<K,V> temp = lruNode;
        while(temp!=null){
            sb.append(temp.key).append(":").append(temp.value);
            sb.append(" -> ");
            temp = temp.next;
        }
        sb.append(" -> mru ");
        return sb.toString();
    }

    public static void main(String[] args) {
        LruCache<String,String> cache = new LruCache<>();
        cache.put("1","1");
        System.out.println(cache);
        cache.get("1");
        cache.put("2","2");
        System.out.println(cache);
        cache.put("3","3");
        System.out.println(cache);
        cache.put("4","4");
        System.out.println(cache);
    }
}

class DoubleListNode<K,V>{
    K key;
    V value;
    DoubleListNode<K,V> pre;
    DoubleListNode<K,V> next;

    public DoubleListNode(K key,V value){
        this.key = key;
        this.value = value;
    }

    public DoubleListNode(DoubleListNode<K,V> pre,DoubleListNode<K,V> next,K key,V value){
        this.pre = pre;
        this.next = next;
        this.key = key;
        this.value = value;
    }
}

여기 서 링크 와 HashMap 을 사용 하여 LRU 기반 캐 시 를 완 성 했 습 니 다. 그 중에서 HashMap 은 주로 빠 른 색인 key, 링크 는 LRU 체 제 를 완성 하 는 데 사 용 됩 니 다.물론 캐 시 제거 remove, 캐 시 ttl, 스 레 드 보안 등 많은 부족 함 이 있 습 니 다.