算法之LFU缓存算法

public class LFUCacheUsingTwoWayLinkedList<K, V> {
    /**
     * 链表尾部的NodeQueue,指向访问次数最少的节点
     */
    public CacheNodeQueue tail;
    /**
     * 容量
     */
    public int capacity;

    public HashMap<K, Pair<Integer,V>> getMap() {
        HashMap<K, Pair<Integer,V>> hashMap = new HashMap<>();
        map.forEach((x,y)->{
            hashMap.put(x,Pair.of(y.currentLevelQueue().frequency,y.value));
        });
        return hashMap;
    }
    /**
     * 存储key-value对的HashMap
     */
    private HashMap<K, CacheNode<K,V>> map;

    //构造方法
    public LFUCacheUsingTwoWayLinkedList(int capacity) {
        this.capacity = capacity;
        map = new HashMap<K, CacheNode<K,V>>(capacity);
    }

    /**
     * Node升级到下一个queue
     * @param n
     */
    private void moveNodeToNextLevelQueueHead(CacheNode n){
        CacheNodeQueue current = n.currentLevelQueue();
        int valueFrequency= current.frequency+1;
        CacheNodeQueue nextLevel = current.high;
        if(current.isHeadQueue()){
            if(current.isSingleQueue()) {
                // 单元素节点直接增加queue的frequency
                current.frequency++;
            }else {
                //在下一级直接加上一个新节点
                unlinkNode(n);
                new CacheNodeQueue(current, null, n, n, valueFrequency);
            }
        }else {
            if (current.high.frequency == valueFrequency) {
                if(current.isSingleQueue()) {
                    unlinkNode(n);
                    nextLevel.addNodeToHead(n);
                    if(current.isTailQueue()){
                        tail = nextLevel;
                        nextLevel.low = null;
                    }else {
                        current.low.high = nextLevel;
                        nextLevel.low = current.low;
                    }
                }else {
                    //下一级NodeQueue的访问次数与Node当前访问次数一样，
                    //把Node插入到下一级NodeQueue的头部
                    unlinkNode(n);
                    nextLevel.addNodeToHead(n);
                }
            }else if (current.high.frequency > valueFrequency) {
                if(current.isSingleQueue()) {
                    if(current.isTailQueue()){
                        current.frequency++;
                    }else {
                        unlinkNode(n);
                        nextLevel = new CacheNodeQueue(current, current.high, n, n, valueFrequency);
                        current.low.high = nextLevel;
                        nextLevel.low = current.low;
                    }
                }else {
                    //下一级NodeQueue的访问次数大于Node当前访问次数，需要在两个NodeQueue之间插入一个新的NodeQueue
                    unlinkNode(n);
                    new CacheNodeQueue(current, current.high, n, n, valueFrequency);
                }
            }
        }
    }

    public V get(K key) {
        CacheNode n = map.get(key);
        if (n == null) {
            return null;
        }
        moveNodeToNextLevelQueueHead(n);
        return (V) n.value;
    }

    public void put(K key, V value) {
        if (capacity == 0) {
            return;
        }

        CacheNode cn = map.get(key);
        //key已存在的情况下，更新value值，并将Node右移
        if (cn != null) {
            cn.value = value;
            moveNodeToNextLevelQueueHead(cn);
            return;
        }
        //cache已满的情况下，把外层链表尾部的内层链表的尾部Node移除
        if (map.size() == capacity) {
            CacheNodeQueue current = tail;
            if(current.isSingleQueue()){
                tail = current.high;
            }
            CacheNode node= unlinkNode(current.tail);
            map.remove(node.key);

        }
        //插入新的Node
        CacheNode n = new CacheNode(key, value);
        if (this.tail == null) {
            //tail为null说明此时cache中没有元素，直接把Node封装到NodeQueue里加入
            CacheNodeQueue nq = new CacheNodeQueue(null, null, n, n,0);
            this.tail = nq;
        } else if (this.tail.frequency == 0) {
            //外层链表尾部元素的访问次数是0，那么将Node加入到外层链表尾部元素的头部
            // 之所以加到头部，是因为要求“如果访问次数相同的元素有多个，则移除最久访问的那个”
            this.tail.addNodeToHead(n);
        } else {
            //外层链表尾部元素的访问次数不是0，那么实例化一个只包含此Node的NodeQueue，加入外层链表尾部
            CacheNodeQueue nq = new CacheNodeQueue( null,this.tail, n, n,0);
            this.tail = nq;
        }
        //最后把key和Node存入HashMap中
        map.put(key, n);
    }
}

public class LFUCacheUsingTreeMap<K, V> {

    Map<K, Node<K,V>> cache;
    /**
     * K是频率，V是按顺序插入的节点
     */
    TreeMap<Integer, LinkedHashSet<Node<K,V>>> freqMap;
    int capacity;

    public LFUCacheUsingTreeMap(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        freqMap = new TreeMap<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K,V> node = cache.get(key);
        //更新访问次数
        refreshFreq(node);
        return node.val;
    }

    public void put(K key, V value) {
        if (capacity == 0) {
            return;
        }
        if (cache.containsKey(key)) {
            Node<K,V> node = cache.get(key);
            node.val = value;
            //更新访问次数
            refreshFreq(node);
        } else {
            if (cache.size() == capacity) {
                //删除频率最低的
                LinkedHashSet<Node<K,V>> nodes = freqMap.get(freqMap.keySet().stream().findFirst().get());
                Node node = nodes.stream().findFirst().get();
                cache.remove(node.key);
                deleteNodeFromFreqMap(node);
            }
            Node node = new Node(key, value);
            cache.put(key, node);
            addNodeToFreqMap(node);
        }
    }

    private void refreshFreq(Node node) {
        deleteNodeFromFreqMap(node);
        node.freq++;
        addNodeToFreqMap(node);
    }

    private void addNodeToFreqMap(Node<K,V> node) {
        if (!freqMap.containsKey(node.freq)) {
            freqMap.put(node.freq, new LinkedHashSet<>());
        }
        freqMap.get(node.freq).add(node);
    }

    private void deleteNodeFromFreqMap(Node<K,V> node) {
        LinkedHashSet<Node<K,V>> nodes = freqMap.get(node.freq);
        // 这里的消耗应该是O(1)级别的
        nodes.remove(node);
        if (nodes.isEmpty()) {
            freqMap.remove(node.freq);
        }
    }
}
class Node<K,V>{
    K key;
    V val;
    int freq;
    public Node(){}
    public Node(K k,V v){
        this.key=k;
        this.val =v;
        this.freq=1;
    }
}