package collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
class LRUCache<K,V> extends LinkedHashMap<K,V>{
    private int maxSize; //緩存的大小
    //重寫
    public LRUCache(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }
    //protected
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
        return size() > maxSize;//根據(jù)大小，決定是否刪除最早結(jié)點
    }
}
public class Teacher_1_15_LinkedHashMap {
    public static void main(String[] args) {
    	//使用LinkedHashMap實現(xiàn)LRU緩存
    	//大小為3
        LRUCache<String, String> cache = new LRUCache<>(3);
        cache.put("a", "jfdshjhf");
        //a
        cache.put("b", "fdjhfjf");
        //a - > b
        cache.put("c", "all");
        //a -> b -> c
        cache.get("a");
        //b -> c -> a
        cache.put("d", "tulun");
        //c -> a -> d
        System.out.println(cache);
        //維護插入順序
//        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
//        map.put(1, "ajhd");
//        map.put(5, "fsd");
//        map.put(12, "ref");
//        map.put(10, "gdfs");
//        map.put(19, "hgf");
//        map.put(21, "hgf");
//
//        Iterator<Integer> iterator = map.keySet().iterator();
//        while(iterator.hasNext()){
//            System.out.println(iterator.next());
//        }
//        //維持訪問順序                                                                                                                                                                                             加載因子：f類型      accessOrder
//        LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>(16, 0.75f, true);
//        map.put(1, "ajhd");
//        map.put(5, "fsd");
//        map.put(12, "ref");
//        map.put(10, "gdfs");
//        map.put(19, "hgf");
//        map.put(21, "hgf");
//
//        map.get(12);
//        map.get(10);
//
//        Iterator<Integer> iterator = map.keySet().iterator();
//        while(iterator.hasNext()){
//            System.out.println(iterator.next());
//        }
    }
}

package collection;
import java.util.HashMap;
import javax.swing.text.html.HTMLDocument.Iterator;
class MyLRUCache<K,V>{
    private Node<K,V> head = new Node<>();//頭結(jié)點    無參構(gòu)造
    private Node<K,V> tail = new Node<>();//尾
    private final HashMap<Integer,Node> hashMap = new HashMap<>();//new了，作為容器
    private int size;  //實際大小
    private int capacity;//最大容量
    class Node<K, V>{
        private K key;
        private V value;
        private Node pre;//雙向鏈表
        private Node next;
        //構(gòu)造器
        public Node(){
        }
        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
    }
    //初始化
    public MyLRUCache(int capacity){
        head.next = tail;//先指向無效的結(jié)點，專門指向 頭和尾
        tail.pre = head;
        this.capacity = capacity;
        size = 0;
    }
    //添加某個節(jié)點（尾插法）
    private void add(Node node){
    	//put里已判斷key是否存在，這里只管添加
    	//空表
    	if(tail.pre==head) {
    		head.next=node;//由head指向node
    		//node為首結(jié)點，前面再無，故不用設置node.pre
    		tail.pre=node;
    	}else {
    		//Tail之后添加
    		node.pre=tail.pre;
    		tail.pre.next=node;
    		tail.pre=node;
    	}	
    }
    //刪除某個節(jié)點
    private void remove(Node node){
    	//非空表
    	if(head.next!=tail) {//比地址
    		//頭結(jié)點
    		if(node==head.next) {
        		head.next=head.next.next; //新頭結(jié)點
        		//head.next.pre=null; //新頭結(jié)點不需要設置pre
        	}else if(node==tail.pre) {
        		//尾結(jié)點
        		tail.pre=tail.pre.pre;//新尾結(jié)點
        		//tail.pre.pre.next=null;
        	}else {
        		//其他
        		node.pre.next=node.next;//要刪除結(jié)點的前面結(jié)點的next指針往后指一個
            	node.next.pre=node.pre;//要刪除結(jié)點的后面結(jié)點的 pre指針往前指一個
        	}   
    	}	
    }
    //添加key-value鍵值對
    public void put(K key, V value){
        Node node = hashMap.get(key);//hashMap里已存有相同key的結(jié)點
        if(node != null){
            node.value = value;
            //從鏈表中刪除node節(jié)點
            remove(node);
            //再將node節(jié)點尾插法重新插入鏈表（因為它剛被訪問）
            add(node);
        }else{
            if(size < capacity){
                size++;
            }else{
                //超容量(1個)，刪除緩存中最近最少使用的節(jié)點head.next
            	//注意先從HashMap里刪除，不然remove會改變head.next值
            	hashMap.remove(head.next.key);//刪除指定key的結(jié)點
            	remove(head.next);//head.next變?yōu)橹赶騢ead.next.next了
            }
            //將newNode尾插法插入鏈表
            Node newNode = new Node(key, value);//將輸入的key value包裝成node
            hashMap.put((Integer) key, newNode);//存到hashMap,鍵為隨機值，值為node結(jié)點        (int)(Math.random()*100)
            add(newNode);
        }
    }
    //獲取value（返回8，表示成功）（將訪問的元素移到鏈表尾）
    public int get(K key){
        Node node = hashMap.get(key);
        if(node == null){
            return -1;
        }
        //刪除node
        hashMap.remove(node.key);//刪除指定key的結(jié)點
        remove(node);
        //尾插法重新插入
        add(node);
        hashMap.put((Integer) key, node);
        //等價于個數(shù)沒變
        return 8;
    }
    public void show() {
    	Node<K,V> temp = head;
    	while(temp!=tail.pre){//tail.pre指向的是末尾節(jié)點
    		temp=temp.next;
    		System.out.print(temp.key+"  ");
    	}
    	System.out.println();
    }
}
public class Teacher_1_15_MyLRUCache {
    public static void main(String[] args) {
      //維護插入順序
      MyLRUCache<Integer, String> cache = new MyLRUCache<>(3);
      cache.put(1, "ajhd");
      cache.put(5, "fsd");
      cache.put(12, "ref");
      cache.show();//應該1 5  12
      System.out.println(cache.get(5));//成功則返回8
      cache.show(); //應該1 12 5
      cache.put(10, "gdfs");
      cache.show();//應該12 5 10
      //如何打印雙向鏈表里的順序
      System.out.println(cache.get(1));
    }
}