LFU算法（Last Frequently Used）

Leetcode : [https://leetcode-cn.com/problems/lfu-cache/)
Diffculty：Hard

要求：get 和 put 操作, 時間復雜度O(1)

LFU算法的設(shè)計原則：
1）put 和 get 操作，都算是使用，freq計數(shù)都得加1
2）如果達到容量限制，移除freq最小的那個Cache
3）移除時，如果有多個Cache的freq相同，那么移除最久未使用的那個（LRU）

設(shè)計思路：
1）使用 Map 來存儲Cache，做到get 的O(1) 時間復雜度。
2）內(nèi)部使用雙鏈表節(jié)點維護緩存隊列，列表頭部是最久未使用的節(jié)點，淘汰時直接淘汰頭部節(jié)點
3）增加一個Map，存儲每一個freq數(shù)字的尾節(jié)點Node對象引用。
每一次操作 get 和 put 都需要對節(jié)點進行移動，具體來講，是需要把該節(jié)點移動到對應freq子列表的尾節(jié)點（即最新使用的）這樣就做到了get 和 put 操作時，移動節(jié)點耗時的 O(1) 時間復雜度。

由于是用的Leetcode的題解直接貼上來，所以Cache就用的是數(shù)字，可以改造為泛型。
代碼：

public class LFUCache {
    /**
     * key=key, val=valNode
     */
    private Map<Integer, Node> valMap;

    /**
     * key=freqNum 也就是調(diào)用次數(shù)
     * val=該次數(shù)的隊伍尾部node指針
     */
    private Map<Integer, Node> freqNumMap;

    /** 雙端隊列 */
    private Node head;
    private Node tail;
    private int capacity;


    public LFUCache(int capacity) {
        this.capacity = capacity;
        valMap = new HashMap<>(capacity);
        freqNumMap = new HashMap<>(capacity);
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre= head;
    }

    public int get(int key) {
        Node node = valMap.get(key);
        if(node==null) {
            return -1;
        }
        freqNode(node, node.freq+1);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = valMap.get(key);
        if(node == null){
            if(valMap.size() == capacity){
                deleteHead();
            }
            if(valMap.size() < capacity){
                addNewNode(key, value);
            }
        }else if(node.val != value){
            node.val = value;
            freqNode(node, node.freq + 1);
        }

    }




    /**
     * 給node設(shè)置freq 并且 根據(jù)freq重置在雙端列表的位置
     * @param node
     * @param newFreq
     */
    private void freqNode(Node node, int newFreq){
        System.out.println("重置Node:" + node + "到freq:" + newFreq);
        // 校驗修改 freqNumMap 指針
        checkAndRemoveFreqTail(node);

        // 找到舊freq對應的Node
        Node freqNode = findFreqNode(newFreq);
        node.freq = newFreq;
        insertNode(freqNode, node);

        // 添加node到freq
        freqNumMap.put(newFreq, node);

    }

    private Node findFreqNode(int freq){
        Node freqNode = freqNumMap.get(freq--);
        while(freqNode==null && freq > 0){
            freqNode = freqNumMap.get(freq--);
        }

        return freqNode==null ? head : freqNode;
    }

    private void addNewNode(int key, int val){
        Node newNode = new Node(key, val, 1, null, null);
        insertNode(head, newNode);
        freqNode(newNode, 1);
        valMap.put(key, newNode);
    }

    private void deleteHead(){
        Node firstNode = head.next;
        if(firstNode == tail){  // 到頭了，刪沒了
            return;
        }
        // 移除valMap 的值
        valMap.remove(firstNode.key);

        // 判斷freqNumMap, 如果是對應freqNum的尾節(jié)點,則更換尾節(jié)點
        checkAndRemoveFreqTail(firstNode);

        // 將節(jié)點從列表中移除(連接前后節(jié)點, 刪除節(jié)點引用)
        firstNode.pre.next = firstNode.next;
        firstNode.next.pre = firstNode.pre;
        firstNode.pre=null;
        firstNode.next=null;

        System.out.println("刪除Node" + firstNode);
        return;
    }

    private void insertNode(Node before, Node node){
        if(node.pre != null){
            node.pre.next = node.next;
        }
        if(node.next != null){
            node.next.pre = node.pre;
        }
        Node after = before.next;
        before.next = node;
        after.pre = node;
        node.pre = before;
        node.next = after;
    }

    private void checkAndRemoveFreqTail(Node node){
        int freq = node.freq;
        if(node == freqNumMap.get(freq)){
            Node preNode = node.pre;
            if(preNode != head && preNode.freq==freq){
                freqNumMap.put(freq, preNode);
            }else{
                freqNumMap.remove(freq);
            }
        }
    }


    private static class Node {
        int key;
        int val;
        int freq;
        Node next;
        Node pre;

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    ", freq=" + freq +
                    '}';
        }

        public Node() {
        }

        public Node(int key, int val, int freq,  Node pre, Node next) {
            this.key = key;
            this.val = val;
            this.freq = freq;
            this.next = next;
            this.pre = pre;
        }
    }
}