简介

LRU（Least Recently Used，最近最少使用）：LRU 是一种基于时间的缓存淘汰策略。最长时间未被访问的数据将被优先移除。

LFU（Least Frequently Used，最不经常使用）：LFU 是一种基于频率的缓存淘汰策略。使用频率最低的数据将被优先移除。如果多个数据的使用频率相同，则删除最久未使用的。

题目

由于力扣有现成的题目，代码实现将遵循题目中规定的接口。

146. LRU 缓存 - 力扣（LeetCode）

460. LFU 缓存 - 力扣（LeetCode）

LRU

思路

采用双端链表+哈希表实现：

  1. 链表节点保存key-value，哈希表将key映射到链表节点；
  2. 每次访问时，将当前访问节点移动到链表尾端，这样链表头部就始终是待删除节点；
  3. 如果新增节点时容量达上限，删除链表头部节点；

当然也可以直接用LinkedHashMap保存键值对，其天然就能保留元素添加顺序（因为其底层也就是双端链表+哈希表）但这样就显得太简单了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Node{
    int key = -1;
    int val = -1;
    Node prev = null;
    Node next = null;
}

class LRUCache {
    Map<Integer, Node> mp = new HashMap<>();
    Node dummyHead = new Node();
    Node dummyTail = new Node();
    int sz;

    public LRUCache(int capacity) {
        this.sz = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        if(!mp.containsKey(key)) return -1;
        Node node = mp.get(key);
        deleteNode(node);
        insertNodeAtTail(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(mp.containsKey(key)){
            Node node = mp.get(key);
            node.val = value;
            deleteNode(node);
            insertNodeAtTail(node);
            mp.put(key, node);
        }
        else{
            Node newNode = new Node();
            newNode.val = value;
            newNode.key = key;
            if(mp.size() == sz){
                Node delNode = dummyHead.next;
                mp.remove(delNode.key);
                deleteNode(delNode);
            } 
            insertNodeAtTail(newNode);
            mp.put(key, newNode);
        }
    }

    public void insertNodeAtTail(Node node){
        Node left = dummyTail.prev;
        left.next = node;
        node.prev = left;
        node.next = dummyTail;
        dummyTail.prev = node;
    }

    public void deleteNode(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }
}

复杂度

函数 get 和 put 的平均时间复杂度均为 O(1) 。

LFU

思路

  1. 自定义双向链表节点Node保存key-value以及访问次数freq；
  2. 定义第一个哈希表维护key到Node的映射关系；
  3. 定义第二个哈希表根据freq定位到一个双向链表，该链表中保存了访问次数为freq的所有Node，并且使用时间越早的Node越靠近链表头部；
  4. 维护当前的最小freq，拿着最小freq取出哈希表中的链表，这个链表的头节点就是待删除节点，因为它的频率最低且最久未使用；
  5. 每次get或put，都要将Node从当前的双向链表中删除，并加到freq+1对应的双向链表中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Node{
    public int key;
    public int val;
    public int freq;
    Node prev = null;
    Node next = null;
}

class LFUCache {
    // 每个key可以定位一个缓存块，每个freq可以定位一个双向链表，双向链表头部即最近最少使用的缓存块
    Map<Integer, Node[]> freq_map = new HashMap<>();    // 双向链表的虚拟头、虚拟尾节点
    Map<Integer, Node> key_map = new HashMap<>();
    int limit = 0;      // 缓存块数量限制
    int minFreq = 0;    // 所有缓存块的freq最小值

    public LFUCache(int capacity) {
        this.limit = capacity;
    }
    
    public int get(int key) {
        if(!key_map.containsKey(key)) return -1;
        Node node = key_map.get(key);
        Node[] tmp = freq_map.get(node.freq);
        Node dummyHead1 = tmp[0], dummyTail1 = tmp[1];
        deleteNode(node);
        if(dummyHead1.next == dummyTail1){
            // freq只对应一个缓存块
            minFreq = minFreq == node.freq ? node.freq + 1 : minFreq;
        }
        node.freq++;
        Node dTail = generateFreq(node);
        insertNodeAtTail(node, dTail);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(!key_map.containsKey(key)){
            if(key_map.size() == limit){
                Node delNode = freq_map.get(minFreq)[0].next;
                deleteNode(delNode);
                key_map.remove(delNode.key);
            }
            Node node = new Node();
            node.freq = 1;
            node.key = key;
            node.val = value;
            Node dTail = generateFreq(node);
            insertNodeAtTail(node, dTail);
            key_map.put(key, node);
            // 只要去除了缓存块，就一定会插入新节点
            // 只要插入了新节点，minFreq就一定变为1
            minFreq = 1;    
        }
        else{
            Node node = key_map.get(key);
            Node[] tmp = freq_map.get(node.freq);
            Node dummyHead1 = tmp[0], dummyTail1 = tmp[1];
            deleteNode(node);
            if(dummyHead1.next == dummyTail1){
                // freq只对应一个缓存块
                minFreq = minFreq == node.freq ? node.freq + 1 : minFreq;
            }
            node.val = value;
            node.freq++;
            Node dTail = generateFreq(node);
            insertNodeAtTail(node, dTail);
        }
    }

    // 返回值：node.freq对应的双向链表的虚拟tail节点；如果不存在此双向链表，则创建
    public Node generateFreq(Node node){
        Node dummyHead = null, dummyTail = null;
        if(!freq_map.containsKey(node.freq)){
            // freq+1第一次出现
            dummyHead = new Node();
            dummyTail = new Node();
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
            freq_map.put(node.freq, new Node[]{dummyHead, dummyTail});
        }
        else dummyTail = freq_map.get(node.freq)[1];
        return dummyTail;
    }

    public void deleteNode(Node node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.next = null;
        node.prev = null;
    }

    public void insertNodeAtTail(Node node, Node dummyTail){
        Node left = dummyTail.prev;
        left.next = node;
        dummyTail.prev = node;
        node.next = dummyTail;
        node.prev = left;
    }
}

复杂度

函数 get 和 put 的平均时间复杂度均为 O(1) 。

__END__