题目描述：

链接：https://leetcode-cn.com/problems/lfu-cache

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

  • LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
  • int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
  • void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

示例：

输入：
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3

额外要求：get和put方法的时间复杂度为O(1)

解题思路：

1、不考虑额外要求，采用hashmap+treemap即可（java中两个数据结构均有实现）。

2、自己的版本（自己实现双链表+两个哈希表，麻烦的地方在于更细minfre）

  1. package leetcode.cache;
  3. import java.util.HashMap;
  5. public class LFUCache {
  7.     private int capacity;
  8.     private int size;
  9.     HashMap<Integer, Node> smap = new HashMap<>();
  10.     HashMap<Integer, DoubleList> fmap = new HashMap<>();
  11.     //找最少频率的策略
  12.     int minfre = Integer.MAX_VALUE;
  13.     Node minfreNode;
  14. //节点
  15.     static class Node {
  16.         Integer key;
  17.         Integer value;
  18.         Node next;
  19.         Node prev;
  20.         int freq;
  22.         public Node(Integer key, Integer value) {
  23.             this.key = key;
  24.             this.value = value;
  25.             freq = 1;
  26.         }
  28.         public Node() {
  29.         }
  30.     }
  31. //双链表
  32.     static class DoubleList {
  33.         Node head;
  34.         Node tail;
  36.         public DoubleList() {
  37.             head = new Node();
  38.             tail = new Node();
  39.             head.next = tail;
  40.             tail.prev = head;
  41.         }
  43.         public void insertAhead(Node node) {
  44.             node.next = head.next;
  45.             head.next.prev = node;
  46.             head.next = node;
  47.             node.prev = head;
  48.         }
  50.         public void remove(Node node) {
  51.             node.next.prev = node.prev;
  52.             node.prev.next = node.next;
  53.         }
  55.         public Node getLast() {
  56.             if (tail.prev == head) {
  57.                 return null;
  58.             }
  59.             return this.tail.prev;
  60.         }
  62.     }
  64.     public LFUCache(int capacity) {
  65.         this.capacity = capacity;
  66.     }
  68.     public int get(int key) {
  69.         Node tmp = smap.get(key);
  70.         if (tmp == null) {
  71.             return -1;
  72.         }
  73.         updateNode(tmp);
  74.         //更新minNode的策略
  75.         if (tmp == minfreNode) {
  76.             DoubleList tmpd = fmap.get(tmp.freq - 1);
  77.             if (tmpd.getLast() != null) {
  78.                 minfreNode = tmpd.getLast();
  79.             } else {
  80.                 minfre = tmp.freq;
  81.             }
  82.         }
  83.         return tmp.value;
  84.     }
  86.     private void updateNode(Node node) {
  87.         DoubleList tmpList = fmap.get(node.freq);
  88.         tmpList.remove(node);
  89.         node.freq++;
  90.         tmpList = fmap.get(node.freq);
  91.         if (tmpList == null) {
  92.             fmap.put(node.freq, new DoubleList());
  93.             tmpList = fmap.get(node.freq);
  94.         }
  95.         tmpList.insertAhead(node);
  96.     }
  98.     public void put(int key, int value) {
  99.         if (capacity == 0) {
  100.             return;
  101.         }
  102.         Node tmp = smap.get(key);
  103.         if (tmp != null) {
  104.             tmp.value = value;
  105.             updateNode(tmp);
  106.             //更新minfre
  107.             if (tmp == minfreNode) {
  108.                 DoubleList tmpd = fmap.get(tmp.freq - 1);
  109.                 if (tmpd.getLast() != null) {
  110.                     minfreNode = tmpd.getLast();
  111.                 } else {
  112.                     minfre = tmp.freq;
  113.                 }
  114.             }
  115.         } else {
  116.             if (size >= capacity) {
  117.                 DoubleList doubleList = fmap.get(minfre);
  118.                 if (minfreNode == doubleList.getLast()) {
  119.                     minfre = Integer.MAX_VALUE;
  120.                     minfreNode = null;
  121.                 }
  122.                 Integer rkey = doubleList.getLast().key;
  123.                 smap.remove(rkey);
  124.                 doubleList.remove(doubleList.getLast());
  125.                 size--;
  126.             }
  127.             Node node = new Node(key, value);
  128.             smap.put(key, node);
  129.             //设置最小频率
  130.             if (node.freq < minfre) {
  131.                 minfreNode = node;
  132.                 minfre = node.freq;
  133.             }
  134.             DoubleList tmpList = fmap.get(node.freq);
  135.             //如果没有对应的频率链表则新创建
  136.             if (tmpList == null) {
  137.                 fmap.put(node.freq, new DoubleList());
  138.                 tmpList = fmap.get(node.freq);
  139.             }
  140.             tmpList.insertAhead(node);
  141.             size++;
  142.         }
  143.     }
  145.    //测试
  146.     public static void main(String[] args) {
  147.         LFUCache lfuCache = new LFUCache(2);
  148.         lfuCache.put(1, 1);
  149.         lfuCache.put(2, 2);
  150.         System.out.println(lfuCache.get(1));
  151.         lfuCache.put(3, 3);
  152.         System.out.println(lfuCache.get(2));
  153.         System.out.println(lfuCache.get(3));
  154.         lfuCache.put(4, 4);
  155.         System.out.println(lfuCache.get(1));
  156.         System.out.println(lfuCache.get(3));
  157.         System.out.println(lfuCache.get(4));
  158.     }
  160. }

2、官方解答

class LFUCache {
    int minfreq, capacity;
    Map<Integer, Node> key_table;
    Map<Integer, LinkedList<Node>> freq_table;

    public LFUCache(int capacity) {
        this.minfreq = 0;
        this.capacity = capacity;
        key_table = new HashMap<Integer, Node>();;
        freq_table = new HashMap<Integer, LinkedList<Node>>();
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        if (!key_table.containsKey(key)) {
            return -1;
        }
        Node node = key_table.get(key);
        int val = node.val, freq = node.freq;
        freq_table.get(freq).remove(node);
        // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
        if (freq_table.get(freq).size() == 0) {
            freq_table.remove(freq);
            if (minfreq == freq) {
                minfreq += 1;
            }
        }
        // 插入到 freq + 1 中
        LinkedList<Node> list = freq_table.getOrDefault(freq + 1, new LinkedList<Node>());
        list.offerFirst(new Node(key, val, freq + 1));
        freq_table.put(freq + 1, list);
        key_table.put(key, freq_table.get(freq + 1).peekFirst());
        return val;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (!key_table.containsKey(key)) {
            // 缓存已满，需要进行删除操作
            if (key_table.size() == capacity) {
                // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                Node node = freq_table.get(minfreq).peekLast();
                key_table.remove(node.key);
                freq_table.get(minfreq).pollLast();
                if (freq_table.get(minfreq).size() == 0) {
                    freq_table.remove(minfreq);
                }
            }
            LinkedList<Node> list = freq_table.getOrDefault(1, new LinkedList<Node>());
            list.offerFirst(new Node(key, value, 1));
            freq_table.put(1, list);
            key_table.put(key, freq_table.get(1).peekFirst());
            minfreq = 1;
        } else {
            // 与 get 操作基本一致，除了需要更新缓存的值
            Node node = key_table.get(key);
            int freq = node.freq;
            freq_table.get(freq).remove(node);
            if (freq_table.get(freq).size() == 0) {
                freq_table.remove(freq);
                if (minfreq == freq) {
                    minfreq += 1;
                }
            }
            LinkedList<Node> list = freq_table.getOrDefault(freq + 1, new LinkedList<Node>());
            list.offerFirst(new Node(key, value, freq + 1));
            freq_table.put(freq + 1, list);
            key_table.put(key, freq_table.get(freq + 1).peekFirst());
        }
    }

}
class Node {
    int key, val, freq;

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

}

两种方法的主要区别在于保存和更新最小频率节点的策略，同时如果是在面试的时候双链表一般会要求自己手动实现。

总结：LRU和LFU的区别与使用场景：

mysql同时使用lfu和lru策略来管理缓存，lfu用于刷新脏页，lru用于管理结果页的缓存。

以下摘自https://www.jianshu.com/p/1f8e36285539：
LRU，最近最少使用，把数据加入一个链表中，按访问时间排序，发生淘汰的时候，把访问时间最旧的淘汰掉。
比如有数据 1，2，1，3，2
此时缓存中已有（1，2）
当3加入的时候，得把后面的2淘汰，变成（3，1）
LFU，最近不经常使用，把数据加入到链表中，按频次排序，一个数据被访问过，把它的频次+1，发生淘汰的时候，把频次低的淘汰掉。
比如有数据 1，1，1，2，2，3
缓存中有（1(3次)，2(2次)）
当3加入的时候，得把后面的2淘汰，变成（1(3次)，3(1次)）
区别：LRU 是得把 1 淘汰。
显然
LRU对于循环出现的数据，缓存命中不高
比如，这样的数据，1，1，1，2，2，2，3，4，1，1，1，2，2，2…..
当走到3，4的时候，1，2会被淘汰掉，但是后面还有很多1，2
LFU对于交替出现的数据，缓存命中不高
比如，1，1，1，2，2，3，4，3，4，3，4，3，4，3，4，3，4……
由于前面被（1(3次)，2(2次)）
3加入把2淘汰，4加入把3淘汰，3加入把4淘汰，然而3，4才是最需要缓存的，1去到了3次，谁也淘汰不了它了。

作者：ck2016
链接：https://www.jianshu.com/p/1f8e36285539
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。