LRU缓存和LFU缓存

  

引言：

操作系统中的页面置换算法是很多缓存机制的基础，比较经典的就有LRU和LFU算法。当缓存数据的数量未达到容量大小时，能正常存入缓存的数据结构中；当缓存的数据容量达到了最大容量，而又有新的数据需要缓存时，就得考虑如何删除已存在的缓存。LRU算法考虑删除最近最长时间未使用的缓存，而LFU考虑删除最近最少被使用的缓存。LRU的关键是看缓存数据最后一次被使用的时间，而LFU关键是看一段时间内缓存数据被使用的频率。不管是获取数据还是添加数据都叫做使用。

一、LRU（Least Recently Used）缓存机制

  设计和实现一个 LRU (最近最少使用) 缓存机制的数据结构。实现 LRUCache 类：

• LRUCache(int capacity)以正整数作为容量 capacity 初始化 LRU 缓存。
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入改组【关键字-值】。当缓存容量达到上限时，它应该在写入数据之前删除最久未使用的数据，从而为新的数据值流出空间。

哈希表 + 双向链表 实现
  LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
  对于 get 操作，首先判断 key 是否存在：如果 key 不存在，则返回 -1；如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
  对于 put 操作，首先判断 key 是否存在：如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
  上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1)O(1) 时间内完成。

Java实现 LRU 缓存机制

public class LRUCache {
    private LinkedList<Node> cache;
    private HashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int capacity) {
        this.cache = new LinkedList<>();
        this.map = new HashMap<>();
        this.cap = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int val = map.get(key).val;
        //利用put方法将该数据提前
        put(key, val);
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key, value);
        if (map.containsKey((key))) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (this.cap == cache.size()) {
                //删除链表最后一个元素
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            //直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }

    /*双链表节点类*/
    class Node {
        public int key;
        public int val;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
}

二、LFU（Least Frequently Used）缓存机制

  设计并实现一个 LFU (最不经常使用) 缓存机制的数据结构，实现 LFU 类:

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

哈希表 + 平衡二叉树 实现
  首先缓存的数据结构中需要有 cnt 表示缓存使用的频率，time 表示缓存的使用时间，key 和 value 表示缓存的键值。比较直观的想法就是我们用哈希表 key_table 以键 key 为索引存储缓存，建立一个平衡二叉树 S 来保持缓存根据 (cnt，time) 双关键字。
  对于 get(key) 操作，我们只要查看一下哈希表 key_table 是否有 key 这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。
  对于 put(key, value) 操作，首先需要查看 key_table 中是否已有对应的键值。如果有的话操作基本等同于 get(key)，不同的是需要更新缓存的 value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量 capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除 key_table 中对应的索引，最后向 key_table 和 S 插入新的缓存信息即可。

Java实现

public class LFUCache{
    private int cap;//容量
    private int time;//时间戳
    HashMap<Integer, Node> key_table;
    TreeSet<Node> cache;

    LFUCache(int capacity){
        this.cap = capacity;
        this.time = 0;
        key_table = new HashMap<>();
        cache = new TreeSet<>();
    }

    public void set(int key, int val){
        if (!key_table.containsKey(key)) {
            if (key_table.size() == cap) {
                // 从哈希表和平衡二叉树中删除最近最少使用的缓存
                key_table.remove(cache.first().key);
                cache.remove(cache.first());
            }
            Node node = new Node(1, ++time, key, val);
            key_table.put(key, node);
            cache.add(node);
        } else {
            Node node = key_table.get(key);
            cache.remove(node);
            node.cnt += 1;
            node.time = ++time;
            node.val = val;
            cache.add(node);
            key_table.put(key, node);
        }
    }

    public int get(int key){
        if(cap == 0) return -1;
        // 如果哈希表中没有键 key，返回 -1
        if(!key_table.containsKey(key)) return -1;
        Node node = key_table.get(key);// 从哈希表中得到旧的缓存
        cache.remove(node);// 从平衡二叉树中删除旧的缓存
        // 将旧缓存更新
        node.cnt += 1;
        node.time = ++time;
        // 将新缓存重新放入哈希表和平衡二叉树中
        cache.add(node);
        key_table.put(key, node);
        return node.val;
    }

    private class Node implements Comparable{
        private int cnt, time, key, val;
        Node(int c, int t, int k, int v){
            this.cnt = c;
            this.time = t;
            this.key = k;
            this.val = v;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            if (cnt != node.cnt) return false;
            if (time != node.time) return false;
            if (key != node.key) return false;
            return val == node.val;
        }

        @Override
        public int hashCode() {
            int result = cnt;
            result = 31 * result + time;
            result = 31 * result + key;
            result = 31 * result + val;
            return result;
        }

        @Override
        public int compareTo(Object o) {
            Node node = (Node) o;
            return cnt == node.cnt ? time - node.time : cnt - node.cnt;
        }
    }
}