0.前言

不管是计算机系统里的Cache缓存，还是现在流行的内存缓存，由于缓存容量的限制，都会设计淘汰算法，即选择哪一块“旧的”数据替换出去，用以存放“最新”的数据。
常见的淘汰算法有：

FIFO：先进先出，最先进入缓存的数据，在缓存空间不足时被清除，为了保证最新数据可用，保证实时性
LRU（Least Recently Used）：最近最久未使用，基于访问次数，去除命中次数最少的元素，保证高频数据有效性
LFU（Least Frequently Used）：最不经常使用，基于访问时间，在被访问过的元素中去除最久未使用的元素，保证热点数据的有效性

1.LRU

一般面试考察LRU的算法题，基本是考察点就是实现双链表，不太可能让你实现哈希表，所以哈希表直接用HashMap即可。
实现 LRUCache 类：

LRUCache(int capacity) ：以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value)：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

实现思路

使用双链表来维护“最近最久未使用”性质，链表表头存放oldest的数据，表尾存放youngest的数据
使用哈希表来维护key-value键值对

每次get时：

如果key不存在，则直接返回-1
如果key存在，则先将该节点从链表中删除，然后将其插入链表末尾，标识刚刚访问过

每次put时：

如果key存在，则更新key对应的值为value，并且将该节点从链表中删除，然后将其插入链表末尾，标识刚刚访问过
如果key不存在，新建节点，放入哈希表中，并将节点放入链表尾部，随后判断缓存容量，如果超了，则执行替换：
- 逐出“最近最久未使用”的节点，即表头节点，同时将对应的key从哈希表中删除
注意：不可直接使用Java中的LinkedList，原因有二：
- LinkedList类的remove(int val)是通过逐个扫描比较来实现的，即时间复杂度O（1）
- 面试官的考点就是让你自己实现双链表

代码实现

class LRUCache {
    int capacity;
    // 双向链表维护LRU性质，head存放oldest,tail存放youngest
    DoubleLinkedList keyCache;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.keyCache = new DoubleLinkedList();
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if ( node == null ) return -1;
        keyCache.removeSpecific(node);
        keyCache.addLast(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        // 如果存在，更新kv，更新lru
        if ( map.containsKey(key) ) {
            Node node = map.get(key);
            node.val = value;
            map.put(key, node);
            // 删除当前访问的节点，放入最后
            keyCache.removeSpecific(node);
            keyCache.addLast(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            keyCache.addLast(node);
            if ( map.size() > capacity ) {
                // 逐出最近最久未使用
                int k_oldest = keyCache.removeFirst();
                map.remove(k_oldest);
            }
        }

    }
}

class Node {
    int key;
    int val;
    Node pre;
    Node next;
    public Node(){}
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        pre = null;
        next = null;
    }
}
class DoubleLinkedList {
    // 虚拟节点，统一操作
    Node head;
    Node tail;

    public DoubleLinkedList() {
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    void addLast(Node node) {
        Node tail_pre = tail.pre;
        tail_pre.next = node;
        node.next = tail;
        node.pre = tail_pre;
        tail.pre = node;
    }
    int removeFirst() {
        Node head_next = head.next;
        int k = head_next.key;
        head.next = head_next.next;
        head_next.next.pre = head;
        return k;
    }
    void removeSpecific(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

}

2.LFU

实现 LFUCache 类：

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

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

实现思路

为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器，使用计数最小的键是最久未使用的键
其他实现思路类似LRU

代码实现

class LFUCache {
    int capacity;
    int minRef;
    // k -> node
    Map<Integer, Node> map;
    // ref -> dlist, 维护LRU
    Map<Integer, DoubleLinkedList> refMap;

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

    public int get(int key) {
        if ( map.containsKey(key) ) {
            Node node = map.get(key);
            // 旧的引用计数链表中删除该节点
            refMap.get(node.ref).removeSpecific(node);

            // 如果dlist没有元素了，refMap中的key也要删除
            if ( refMap.get(node.ref).size == 0 ) {
                refMap.remove(node.ref);
            }

            // 引用计数+1
            node.ref++;
            minRef = Math.min(minRef, node.ref);
            map.put(key, node);

            // node插入新的引用计数(+1后的)链表
            DoubleLinkedList cur_ref_list = refMap.get(node.ref);
            if ( null == cur_ref_list ) {
                // 新建链表
                cur_ref_list = new DoubleLinkedList();
                cur_ref_list.addLast(node);
                refMap.put(node.ref, cur_ref_list);
            } else {
                cur_ref_list.addLast(node);
            }
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if ( capacity == 0 ) return;
        if ( map.containsKey(key) ) {
            Node node = map.get(key);
            node.val = value;
            // 旧的refMap删除当前ref对应的kv
            refMap.get(node.ref).removeSpecific(node);

            if ( refMap.get(node.ref).size == 0 ) {
                refMap.remove(node.ref);
            }
            node.ref++;
            minRef = Math.min(minRef, node.ref);
            map.put(key, node);

            DoubleLinkedList cur_ref_list = refMap.get(node.ref);
            if ( null == cur_ref_list ) {
                // 新建链表
                cur_ref_list = new DoubleLinkedList();
                cur_ref_list.addLast(node);
                refMap.put(node.ref, cur_ref_list);
            } else {
                cur_ref_list.addLast(node);
            }
        } else {
            if ( map.size() == capacity ) {
                // 先按minRef
                DoubleLinkedList min_ref_list = refMap.get(minRef);
                while ( min_ref_list == null ) {
                    min_ref_list = refMap.get(++minRef);
                }
                // 相同的minRef下，删除LRU
                int k = min_ref_list.removeFirst();
                if ( min_ref_list.size == 0 ) {
                    refMap.remove(minRef);
                    minRef++;
                }
                map.remove(k);
            }
            Node node = new Node(key, value);
            minRef = Math.min(minRef, node.ref);
            map.put(key, node);

            DoubleLinkedList cur_ref_list = refMap.get(node.ref);
            if ( null == cur_ref_list ) {
                // 新建链表
                cur_ref_list = new DoubleLinkedList();
                cur_ref_list.addLast(node);
                refMap.put(node.ref, cur_ref_list);
            } else {
                cur_ref_list.addLast(node);
            }
        }
    }
}
class Node {
    int key;
    int val;
    int ref;
    Node pre;
    Node next;
    public Node(){}
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        this.ref = 1;
        pre = null;
        next = null;
    }
}
class DoubleLinkedList {
    // 虚拟节点，统一操作
    Node head;
    Node tail;
    int size;
    public DoubleLinkedList() {
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
        size = 0;
    }
    void addLast(Node node) {
        Node tail_pre = tail.pre;
        tail_pre.next = node;
        node.next = tail;
        node.pre = tail_pre;
        tail.pre = node;
        size++;
    }
    int removeFirst() {
        Node head_next = head.next;
        int k = head_next.key;
        head.next = head_next.next;
        head_next.next.pre = head;
        size--;
        return k;
    }
    void removeSpecific(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
    }
}

算法与数据结构

LRU LFU

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

InnoDB存储引擎中的索引上一篇

MySQL中的「锁」与「事务」下一篇

实现LRU/LFU缓存

0.前言

1.LRU

实现思路

代码实现

2.LFU

实现思路

代码实现