LFU缓存

来源力扣第460题LFU缓存

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

• get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
• put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

两个Map实现

利用一个Map存放key到value值的映射，一个Map存放key到freq的映射，由于题目要求当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键，因而采用linkedHashMap实现平局，默认是插入顺序，true为访问顺序

class LFUCache{

    private int capacity;

    private HashMap<Integer,Integer> map1;  //key -> value
    private HashMap<Integer,Integer> map2;  //key -> freq

    public LFUCache(int capacity) {
        this.capacity = capacity;
        map1 = new HashMap<>(capacity);
        //用linkedHashMap实现平局，默认是插入顺序，true为访问顺序
        map2 = new LinkedHashMap<>(capacity,0.75F,true);
    }

    public int get(int key) {
        if(map1.containsKey(key)){
            map2.put(key,map2.get(key)+1);
            return map1.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if(capacity == 0)
            return;
        if(map1.containsKey(key)){
            map1.put(key,value);
            map2.put(key,map2.get(key)+1);
        }else{
            if(map1.size() == capacity){
                int min = Integer.MAX_VALUE;
                int temp = key;
                for(Map.Entry<Integer,Integer> entry : map2.entrySet()){
                    if(min > entry.getValue()){
                        temp = entry.getKey();
                        min = entry.getValue();
                    }
                }
                map1.remove(temp);
                map2.remove(temp);
            }
            map1.put(key,value);
            map2.put(key,1);
        }
    }

}

双向链表

来自sweetiee

HashMap cache 存缓存的内容; 将写法 1 写法 2 中的 freqMap 不再用 HashMap 来表示，而是直接用双向链表 DoubleLinkedList firstLinkedList; DoubleLinkedList lastLinkedList，省去了一些哈希相关的耗时，也不需要用 min 来存储最小频次了，lastLinkedList.pre 这条 DoubleLinkedList 即为最小频次对应的 Node 双向链表，lastLinkedList.pre.tail.pre 这个 Node 即为最小频次的双向链表中的所有 Node 中最先访问的 Node，即容量满了后要删除的 Node。

class LFUCache {

    Map<Integer, Node> cache;  // 存储缓存的内容，Node中除了value值外，还有key、freq、所在DoubleLinkedList、
    // 所在DoubleLinkedList中的postNode、所在DoubleLinkedList中的preNode，具体定义在下方。

    DoubleLinkedList firstLinkedList; // firstLinkedList.post 是频次最大的双向链表
    DoubleLinkedList lastLinkedList;  // lastLinkedList.pre 是频次最小的双向链表，满了之后
    // 删除 lastLinkedList.pre.tail.pre 这个Node即为频次最小且访问最早的Node

    int size;
    int capacity;

    public LFUCache(int capacity) {
        cache = new HashMap<> (capacity);
        firstLinkedList = new DoubleLinkedList();
        lastLinkedList = new DoubleLinkedList();
        firstLinkedList.post = lastLinkedList;
        lastLinkedList.pre = firstLinkedList;
        this.capacity = capacity;
    }



    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }

        // 该key访问频次+1
        freqInc(node);
        return node.value;
    }



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

        Node node = cache.get(key);
        // 若key存在，则更新value，访问频次+1
        if (node != null) {
            node.value = value;
            freqInc(node);
        } else {
            // 若key不存在
            if (size == capacity) {
                // 如果缓存满了，删除lastLinkedList.pre这个链表（即表示最小频次的链表）中的tail.pre这个Node
                // （即最小频次链表中最先访问的Node），如果该链表中的元素删空了，则删掉该链表。
                cache.remove(lastLinkedList.pre.tail.pre.key);
                lastLinkedList.removeNode(lastLinkedList.pre.tail.pre);
                size--;
                if (lastLinkedList.pre.head.post == lastLinkedList.pre.tail) {
                    removeDoubleLinkedList(lastLinkedList.pre);
                }
            }
            // cache中put新Key-Node对儿，并将新node加入表示freq为1的DoubleLinkedList中，
            // 若不存在freq为1的DoubleLinkedList则新建。
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            if (lastLinkedList.pre.freq != 1) {
                DoubleLinkedList newDoublyLinedList = new DoubleLinkedList(1);
                addDoubleLinkedList(newDoublyLinedList, lastLinkedList.pre);
                newDoublyLinedList.addNode(newNode);
            } else {
                lastLinkedList.pre.addNode(newNode);
            }
            size++;
        }
    }


    /**
     * node的访问频次 + 1
     */
    void freqInc(Node node) {
        // 将node从原freq对应的双向链表里移除, 如果链表空了则删除链表。
        DoubleLinkedList linkedList = node.DoubleLinkedList;
        DoubleLinkedList preLinkedList = linkedList.pre;
        linkedList.removeNode(node);
        if (linkedList.head.post == linkedList.tail) {
            removeDoubleLinkedList(linkedList);
        }
        // 将node加入新freq对应的双向链表，若该链表不存在，则先创建该链表。
        node.freq++;
        if (preLinkedList.freq != node.freq) {
            DoubleLinkedList newDoublyLinedList = new DoubleLinkedList(node.freq);
            addDoubleLinkedList(newDoublyLinedList, preLinkedList);
            newDoublyLinedList.addNode(node);
        } else {
            preLinkedList.addNode(node);
        }
    }


    /**
     * 增加代表某1频次的双向链表
     */
    void addDoubleLinkedList(DoubleLinkedList newDoublyLinedList, DoubleLinkedList preLinkedList) {
        newDoublyLinedList.post = preLinkedList.post;
        newDoublyLinedList.post.pre = newDoublyLinedList;
        newDoublyLinedList.pre = preLinkedList;
        preLinkedList.post = newDoublyLinedList;
    }


    /**
     * 删除代表某1频次的双向链表
     */
    void removeDoubleLinkedList(DoubleLinkedList DoubleLinkedList) {
        DoubleLinkedList.pre.post = DoubleLinkedList.post;
        DoubleLinkedList.post.pre = DoubleLinkedList.pre;
    }

}



class Node {

    int key;
    int value;
    int freq = 1;
    Node pre; // Node所在频次的双向链表的前继Node
    Node post; // Node所在频次的双向链表的后继Node
    DoubleLinkedList DoubleLinkedList;  // Node所在频次的双向链表

    public Node() {}

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }

}



class DoubleLinkedList {

    int freq; // 该双向链表表示的频次

    DoubleLinkedList pre;  // 该双向链表的前继链表（pre.freq < this.freq）
    DoubleLinkedList post; // 该双向链表的后继链表 (post.freq > this.freq)

    Node head; // 该双向链表的头节点，新节点从头部加入，表示最近访问
    Node tail; // 该双向链表的尾节点，删除节点从尾部删除，表示最久访问



    public DoubleLinkedList() {
        head = new Node();
        tail = new Node();
        head.post = tail;
        tail.pre = head;
    }



    public DoubleLinkedList(int freq) {
        head = new Node();
        tail = new Node();
        head.post = tail;
        tail.pre = head;
        this.freq = freq;
    }



    void removeNode(Node node) {
        node.pre.post = node.post;
        node.post.pre = node.pre;
    }



    void addNode(Node node) {
        node.post = head.post;
        head.post.pre = node;
        head.post = node;
        node.pre = head;
        node.DoubleLinkedList = this;
    }
    
}

weiwei

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

public class LFUCache {

    /**
     * key 就是题目中的 key
     * value 是结点类
     */
    private Map<Integer, ListNode> map;

    /**
     * 访问次数哈希表，使用 ListNode[] 也可以，不过要占用很多空间
     */
    private Map<Integer, DoubleLinkedList> frequentMap;

    /**
     * 外部传入的容量大小
     */
    private Integer capacity;

    /**
     * 全局最高访问次数，删除最少使用访问次数的结点时会用到
     */
    private Integer minFrequent = 1;


    public LFUCache(int capacity) {
        map = new HashMap<>(capacity);
        frequentMap = new HashMap<>();
        this.capacity = capacity;
    }

    /**
     * get 一次操作，访问次数就增加 1；
     * 从原来的链表调整到访问次数更高的链表的表头
     *
     * @param key
     * @return
     */
    public int get(int key) {
        // 测试测出来的，capacity 可能传 0
        if (capacity == 0) {
            return -1;
        }

        if (map.containsKey(key)) {
            // 获得结点类
            ListNode listNode = removeListNode(key);

            // 挂接到新的访问次数的双向链表的头部
            int frequent = listNode.frequent;
            addListNode2Head(frequent, listNode);
            return listNode.value;
        } else {
            return -1;
        }
    }

    /**
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        // 如果 key 存在，就更新访问次数 + 1，更新值
        if (map.containsKey(key)) {
            ListNode listNode = removeListNode(key);

            // 更新 value
            listNode.value = value;
            int frequent = listNode.frequent;
            addListNode2Head(frequent, listNode);
            return;
        }

        // 如果 key 不存在
        // 1、如果满了，先删除访问次数最小的的末尾结点，再删除 map 里对应的 key
        if (map.size() == capacity) {
            // 1、从双链表里删除结点
            DoubleLinkedList doubleLinkedList = frequentMap.get(minFrequent);
            ListNode removeNode = doubleLinkedList.removeTail();

            // 2、删除 map 里对应的 key
            map.remove(removeNode.key);
        }

        // 2、再创建新结点放在访问次数为 1 的双向链表的前面
        ListNode newListNode = new ListNode(key, value);
        addListNode2Head(1, newListNode);
        map.put(key, newListNode);

        // 【注意】因为这个结点是刚刚创建的，最少访问次数一定为 1
        this.minFrequent = 1;
    }

    // 以下部分主要是结点类和双向链表的操作

    /**
     * 结点类，是双向链表的组成部分
     */
    private class ListNode {
        private int key;
        private int value;
        private int frequent = 1;
        private ListNode pre;
        private ListNode next;

        public ListNode() {
        }

        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 双向链表
     */
    private class DoubleLinkedList {
        /**
         * 虚拟头结点，它无前驱结点
         */
        private ListNode dummyHead;
        /**
         * 虚拟尾结点，它无后继结点
         */
        private ListNode dummyTail;

        /**
         * 当前双向链表的有效结点数
         */
        private int count;

        public DoubleLinkedList() {
            // 虚拟头尾结点赋值多少无所谓
            this.dummyHead = new ListNode(-1, -1);
            this.dummyTail = new ListNode(-2, -2);

            dummyHead.next = dummyTail;
            dummyTail.pre = dummyHead;
            count = 0;
        }

        /**
         * 把一个结点类添加到双向链表的开头（头部是最新使用数据）
         *
         * @param addNode
         */
        public void addNode2Head(ListNode addNode) {
            ListNode oldHead = dummyHead.next;
            // 两侧结点指向它
            dummyHead.next = addNode;
            oldHead.pre = addNode;
            // 它的前驱和后继指向两侧结点
            addNode.pre = dummyHead;
            addNode.next = oldHead;
            count++;
        }

        /**
         * 把双向链表的末尾结点删除（尾部是最旧的数据，在缓存满的时候淘汰）
         *
         * @return
         */
        public ListNode removeTail() {
            ListNode oldTail = dummyTail.pre;
            ListNode newTail = oldTail.pre;

            // 两侧结点建立连接
            newTail.next = dummyTail;
            dummyTail.pre = newTail;

            // 它的两个属性切断连接
            oldTail.pre = null;
            oldTail.next = null;

            // 重要：删除一个结点，当前双向链表的结点个数少 1
            count--;

            // 维护
            return oldTail;
        }
    }


    /**
     * 将原来访问次数的结点，从双向链表里脱离出来
     *
     * @param key
     * @return
     */
    private ListNode removeListNode(int key) {
        // 获得结点类
        ListNode deleteNode = map.get(key);

        ListNode preNode = deleteNode.pre;
        ListNode nextNode = deleteNode.next;
        // 两侧结点建立连接
        preNode.next = nextNode;
        nextNode.pre = preNode;
        // 删除去原来两侧结点的连接
        deleteNode.pre = null;
        deleteNode.next = null;

        // 维护双链表结点数
        frequentMap.get(deleteNode.frequent).count--;

        // 【注意】维护 minFrequent
        // 如果当前结点正好在最小访问次数的链表上，并且移除以后结点数为 0，最小访问次数需要加 1
        if (deleteNode.frequent == minFrequent && frequentMap.get(deleteNode.frequent).count == 0) {
            minFrequent++;
        }

        // 访问次数加 1
        deleteNode.frequent++;
        return deleteNode;
    }


    /**
     * 把结点放在对应访问次数的双向链表的头部
     *
     * @param frequent
     * @param addNode
     */
    private void addListNode2Head(int frequent, ListNode addNode) {
        DoubleLinkedList doubleLinkedList;

        // 如果不存在，就初始化
        if (frequentMap.containsKey(frequent)) {
            doubleLinkedList = frequentMap.get(frequent);
        } else {
            doubleLinkedList = new DoubleLinkedList();
        }

        // 添加到 DoubleLinkedList 的表头
        doubleLinkedList.addNode2Head(addNode);
        frequentMap.put(frequent, doubleLinkedList);
    }
}