손 찢 기 시간 복잡 도가 O (1) 인 LRU 알고리즘

LRU 알고리즘
LRU (Least Recently Used), 즉 최근 알고리즘 을 최소 화한 다.간단 한 캐 시 기능 을 실현 하 는 데 자주 사용 되 는 것 은 오랫동안 사용 하지 않 았 던 것 을 직접 제거 하고 최근 에 사용 한 것 만 유지 하 는 것 이다.
LRU 는 주로 두 가지 기능 을 실현 해 야 한다.
캐 시 추가 (캐 시 삭제 관련) 캐 시 가 져 오기
원 리 를 실현 하 는 단일 체인 표 는 간단 한 LRU 알고리즘 을 실현 할 수 있 습 니 다. 그러나 체인 표 의 검색 시간 은 복잡 도가 비교적 높 고 O (n) 입 니 다.
하나의 산 목록 + 더 블 링크 는 O (1) 복잡 도 를 구현 하 는 LRU 알고리즘 입 니 다. 산 목록 으로 캐 시 를 직접 찾 을 수 있 습 니 다. 시간 복잡 도 O (1) 이지 만 산 목록 에 캐 시 를 삽입 하면 순서 가 없습니다. 따라서 캐 시 순 서 를 유지 하기 위해 서 는 하나의 링크 가 필요 합 니 다. 캐 시 최대 용량 을 초과 한 후에 사용 하지 않 은 캐 시 를 삭제 해 야 합 니 다.단일 링크 에서 캐 시 를 삭제 하려 면 이 요소 (시간 복잡 도 O (n) 를 먼저 옮 겨 다 녀 야 합 니 다.그래서 여기 서 더 블 링크 를 사용 하면 O (1) 시간 복잡 도 에서 이 캐 시 를 삭제 할 수 있 습 니 다.

package com.arithmetic.code;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private int cacheSize = 10; // map   
    private Map<String,Node> map = new HashMap<>();
    private Node head; //     
    private Node tail; //     

    public void LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    class Node{
        String key;
        String value;
        Node pre; //          
        Node next; //          
        
        public Node(String key,String value){
            this.key = key;
            this.value = value;
        }
    }

    /**
     *        ，head      ，tail    
     *           ，                 
     */
    public void  addCache(String key,String value){
        if(map.containsKey(key)){
            //   Node    
            Node node = map.get(key);
            if(node.next != null){ //   node         
                if(node.pre == null){ // node    
                    head = node.next;
                    //   ：  head     pre  null，    ，                  
                    head.pre = null;
                } else { // node      
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                //   node     
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            }
        } else { // map       
            Node node = new Node(key,value);
            if(map.size() == cacheSize){ // map        
                //        ，           
                Node temp = head;
                head = head.next;
                //   head     pre  null
                head.pre = null;
                map.remove(temp.key);
                //   node     
                tail.next = node;
                node.pre = tail;
                node.next = null;
                tail = node;
            } else {
                if(map.size() == 0){
                    head = node;
                    tail = node;
                } else {
                    tail.next = node;
                    node.pre = tail;
                    //   head     pre  null
                    node.next = null;
                    tail = node;
                }
            }
            map.put(key,node);
        }
    }

	//          
    public String getCache(String key){
        if(map.containsKey(key)){ //       key
            Node node = map.get(key);
            if(node.next != null){
                if(node.pre == null){ //      
                    head = node.next;
                    //   head     pre  null
                    head.pre = null;
                } else {
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                node.pre = tail;
                tail.next = node;
                node.next = null;
                tail = node;
            }
            return node.value;
        } else {
            return null;
        }
    }

	//     
    public static void main(String[] args) {
        LRUCache cache = new LRUCache();
        cache.addCache("key0", "value0");
        cache.addCache("key1", "value1");
        cache.addCache("key2", "value2");
        cache.addCache("key3", "value3");
        cache.addCache("key4", "value4");
        cache.addCache("key5", "value5");
        cache.addCache("key6", "value6");
        cache.addCache("key7", "value7");
        cache.addCache("key8", "value8");
        cache.addCache("key9", "value9");
        //     map  ，            ，        
        cache.addCache("key10", "value10");
        cache.addCache("key11", "value11");
        cache.addCache("key12", "value12");
        // debug        node  head  key4，tail  key13
        cache.addCache("key13", "value13");
        // debug     map head  key5，tail  key4（            ）
        cache.getCache("key4");
    }
}