LFU缓存替换算法：least frequency unused 缓存替换算法_lru longest recent unused cache

LFU缓存替换算法：least frequency unused 缓存替换算法

提示：LUR和LFU原理都类似的
之前讲过LRUCache：
LRU缓存内存替换算法：least recently unused 缓存内存替换算法

现在来讲LFUCache

文章目录

• LFU缓存替换算法：least frequency unused 缓存替换算法
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 总结

题目

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

实现 LFUCache 类：

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、审题

示例：
熟悉LRUCache的话，就知道LFU只需要在LRU上面多一个嵌入的frequency维度
即一个2维双向链表

看本题之前，一定把这个文章看了，了解LRU怎么实现的：
LRU缓存内存替换算法：least recently unused 缓存内存替换算法
看懂了LRU，就很容易理解LFU

不妨设capacity=3
put(A,17)
put(B,13)
put(C,1)
这3个都是操作频次为1的
现在这个双向链表就是LRU，按照使用时间顺序链接的，up和down指针相连的。

get©
C现在操作频次为2了，显然不是1，AB还是1，独立开来

其实现在LRFU由2个桶构成，桶1频次为1，桶2频次为2，
桶和桶之间是last和next指针链接

put(D,10)
此时ABC已经是满足容量了，所以要挤出去一个，挤出去谁呢？自然是频率count最低的那个桶（一个桶内就一个LRU），然后要删除head，操作就是LRU中的操作。

put(B,15)
然后，又操作B，B要去2频次的桶，而且比C晚一点

put(B,17)
再一次操作B，频次为3，自然要新增一个桶

count=1的频次最低，也即最左边的桶mostLeft
每次挤兑出去的一定是mostLeft中的head
这就是LFU
是不是有了LRU就能很容易理解？

二、解题

看了案例就知道，这就是LRU上多了一个频次维度，仅此而已
当然，代码非常考验细节！！！
联系coding能力
我看的是左神的代码：

桶的内部，是一个二维的双向链表，每一个节点有2个指针，这个节点被操作了几次，用times记录

// 节点的数据结构
    public static class Node {
        public Integer key;
        public Integer value;
        public Integer times; // 这个节点发生get或者set的次数总和
        public Node up; // 节点之间是双向链表所以有上一个节点
        public Node down;// 节点之间是双向链表所以有下一个节点

        public Node(int k, int v, int t) {
            key = k;
            value = v;
            times = t;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LRU操作的是NDLL
而LFU操作的是桶Bucket,桶比NDLL多了last和next指针（在同种，NDLL的last和next被称为up和down）
（1）Bucket内部某一个桶，它有节点吗？没有就是空，需要有判断函数：isEmpty()
（2）给桶新加一个节点，放入头addNodeFromHead（x）
（3）删除桶中的某个节点：分为删除头，中间x和尾，分情况讨论，删除方法不一样

// 桶结构
    public static class Bucket {//{}--{}--{}中的{}，
        // 它内部装了一串双向量表，有head和tail，它自己还有左右接指针last和next
        public Node head; // 桶的头节点
        public Node tail; // 桶的尾节点
        public Bucket last; // 桶之间是双向链表所以有前一个桶---这就是二维双向链表？？？？牛
        public Bucket next; // 桶之间是双向链表所以有后一个桶

        public Bucket(Node node) {//新建一个桶，必须给一个节点，至少
            head = node;
            tail = node;
        }

        // 把一个新的节点加入这个桶，新的节点都放在顶端变成新的头部,
        // 删除的时候就是最左侧桶的尾部，旧
        public void addNodeFromHead(Node newHead) {
            newHead.down = head;
            head.up = newHead;
            head = newHead;//挪上去
        }

        // 判断这个桶是不是空的
        public boolean isEmpty() {
            return head == null;
        }

        // 删除桶中的node节点，并保证node的上下环境重新连接
        public void deleteNode(Node node) {
            if (head == tail) {//一个节点，全部删除
                head = null;
                tail = null;
            } else {
                //多个节点
                if (node == head) {//是头
                    head = node.down;
                    head.up = null;
                } else if (node == tail) {//是尾
                    tail = node.up;
                    tail.down = null;
                } else {//中间节点，跳过直连
                    node.up.down = node.down;
                    node.down.up = node.up;
                }
            }

            node.up = null;
            node.down = null;//断开node前后，表示消失
        }
    }///桶结构结束
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

拿着这个桶，实现LFU
（1）LFU属性：
——capacity，最多能缓存几个点？容量
——size目前已经缓存了几个点？
——哈希表：keyNodeMap,key的代表节点Node：代表Father
——头桶headBucket（leftMost最左测那个桶）

（2）这个函数:boolean modifyHeadBucket(Bucket removeNodeBucket)
判断刚刚减少了一个节点的桶是不是已经空了。
removeNodeBucket：刚刚减少了一个节点的那个桶
——如果不空，什么也不做

——如果空了，假如removeNodeBucket还是整个缓存结构最左的桶(headBucket)。
则：删掉这个桶的同时，也要让最左的桶变成removeNodeBucket的下一个。

——如果空了，假如removeNodeBucket不是整个缓存结构最左的桶(headBucket)。
则：把这个桶删除，并保证上一个的桶和下一个桶之间还是双向链表的连接方式

函数的返回值表示刚刚减少了一个节点的桶是不是已经空了，空了返回true；不空返回false

（3）移动move(Node node, Bucket oldBucket) 函数
由于操作来了，node这个节点的次数+1了，这个节点原来在oldBucket里。既然频次增加了，就需要放到跟高一个频次的桶中，所以：
把node从oldBucket删掉，然后放到次数+1的桶中接入尾部
整个过程既要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表
显然，oldBucket的上一个桶preBucket需要知道是谁？
oldBucket的下一个桶nextBucket也需要知道是谁？

（4）新加节点函数add（key，value）
——有了就是更新
——没有就是新加，容量多了，先移除最左边桶的头，然后加入最左边桶的尾部，和LRU一样

（5）获取key，get（x）
只需要将其移动到高频次那个桶
很复杂，了解核心思想即可：

//LFUCache数据结构--
    //有了桶，桶中有一串链表，就可以整一个最左侧的桶，开始一个桶一个桶地往下挂接，形成一个二维链表
    //第一维度：headBucket--{}--{}--{}
    //二维度：每一个桶中有一串链表：{head--Node-tail}

    private int capacity; // 缓存的大小限制，即K
    private int size; // 缓存目前有多少个节点
    private HashMap<Integer, Node> keyNodeMap;// 表示key(Integer)由哪个节点(Node)代表
    private HashMap<Node, Bucket> nodeBucketMap; // 表示节点(Node)在哪个桶(Bucket)里--重点
    private Bucket headBucket; // 整个结构中位于最左的桶---最左侧的桶


    // 本题测试链接 : https://leetcode.com/problems/lfu-cache/
    // 提交时把类名和构造方法名改为 : LFUCache
    public Top89LFU(int K) {//初始化这个缓存机制的数据结构时，需要告诉缓存的容量K
        capacity = K;
        size = 0;//现在有几个节点？
        keyNodeMap = new HashMap<>();
        nodeBucketMap = new HashMap<>();
        headBucket = null;
    }

    // removeNodeBucket：刚刚减少了一个节点的桶
    // 这个函数的功能是，判断刚刚减少了一个节点的桶是不是已经空了。
    // 1）如果不空，什么也不做
    //
    // 2)如果空了，removeNodeBucket还是整个缓存结构最左的桶(headBucket)。
    // 删掉这个桶的同时也要让最左的桶变成removeNodeBucket的下一个。
    //
    // 3)如果空了，removeNodeBucket不是整个缓存结构最左的桶(headBucket)。
    // 把这个桶删除，并保证上一个的桶和下一个桶之间还是双向链表的连接方式
    //
    // 函数的返回值表示刚刚减少了一个节点的桶是不是已经空了，
    // 空了返回true；不空返回false
    private boolean modifyHeadBucket(Bucket removeNodeBucket) {
        if (removeNodeBucket.isEmpty()) {
            //桶空了
            if (headBucket == removeNodeBucket) {
                headBucket = removeNodeBucket.next;//更新最左侧的桶
                if (headBucket != null) {
                    headBucket.last = null;//断开之前的桶
                }
            } else {
                //最左侧的桶，不是刚刚删除了一个节点的桶--跳过本桶直连前后，与链表类似
                removeNodeBucket.last.next = removeNodeBucket.next;
                if (removeNodeBucket.next != null) {//确实后面还要，就要跳指
                    removeNodeBucket.next.last = removeNodeBucket.last;
                }
            }
            return true;
        }
        //不空无所谓
        return false;
    }

    // 函数的功能
    // node这个节点的次数+1了，这个节点原来在oldBucket里。
    // 把node从oldBucket删掉，然后放到次数+1的桶中
    // 整个过程既要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表
    private void move(Node node, Bucket oldBucket) {
        oldBucket.deleteNode(node);
        // preBucket表示次数+1的桶的前一个桶是谁
        // 如果oldBucket删掉node之后还有节点，oldBucket就是次数+1的桶的前一个桶，就是node所在的桶
        // 如果oldBucket删掉node之后空了，
        // oldBucket是需要删除的，所以次数+1的桶的前一个桶，是oldBucket的前一个
        Bucket preBucket = modifyHeadBucket(oldBucket) ? oldBucket.last : oldBucket;
        // nextBucket表示次数+1的桶的后一个桶是谁
        Bucket nextBucket = oldBucket.next;
        if (nextBucket == null) {
            Bucket newBucket = new Bucket(node);//因为操作频次+1了，右边没有桶的话，就需要生成一个再放入
            if (preBucket != null) {
                preBucket.next = newBucket;
            }
            newBucket.last = preBucket;
            if (headBucket == null) {
                headBucket = newBucket;
            }
            nodeBucketMap.put(node, newBucket);
        } else {//后面的桶不是空的，有
            if (nextBucket.head.times.equals(node.times)) {//而且频次确实是本次操作之后+1的频次
                nextBucket.addNodeFromHead(node);//然后加进去就行
                nodeBucketMap.put(node, nextBucket);//同步记录节点的地址
            } else {//频次不一样，依然需要重新生成一个桶
                Bucket newBucket = new Bucket(node);
                if (preBucket != null) {
                    preBucket.next = newBucket;
                }
                newBucket.last = preBucket;
                newBucket.next = nextBucket;
                nextBucket.last = newBucket;
                if (headBucket == nextBucket) {
                    headBucket = newBucket;
                }
                nodeBucketMap.put(node, newBucket);
            }
        }
    }

    //新加节点
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (keyNodeMap.containsKey(key)) {//修改值
            Node node = keyNodeMap.get(key);
            node.value = value;
            node.times++;
            Bucket curNodeList = nodeBucketMap.get(node);
            move(node, curNodeList);//完成移动工作
        } else {
            if (size == capacity) {//已经放满了节点，需要干掉之前的最低频的那个节点，然后才能新加
                Node node = headBucket.tail;
                headBucket.deleteNode(node);//需要删除那个最久没用的
                modifyHeadBucket(headBucket);
                keyNodeMap.remove(node.key);
                nodeBucketMap.remove(node);
                size--;//这样才有一个空间给新来的数据添加机会
            }
            Node node = new Node(key, value, 1);//新来的频次为1
            if (headBucket == null) {
                headBucket = new Bucket(node);//没有桶
            } else {
                if (headBucket.head.times.equals(node.times)) {
                    headBucket.addNodeFromHead(node);//最左边那个确实是为1频次
                } else {//否则就要造一个1频次的桶
                    Bucket newBucket = new Bucket(node);
                    newBucket.next = headBucket;
                    headBucket.last = newBucket;
                    headBucket = newBucket;
                }
            }
            keyNodeMap.put(key, node);//同步记录刚刚来的这个bucket和节点的关系
            nodeBucketMap.put(node, headBucket);
            size++;//新增一条记录
        }
    }

    //获取key
    public int get(int key) {
        if (!keyNodeMap.containsKey(key)) {
            return -1;
        }
        Node node = keyNodeMap.get(key);//有，操作频次++
        node.times++;
        Bucket curNodeList = nodeBucketMap.get(node);
        move(node, curNodeList);//完成移动操作--当前所在的桶就是旧桶的位置
        return node.value;
    }
    //思想要搞明白，大厂有人考过………………
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

总结

提示：重要经验：

1）LFU就是LRU的扩展，然后多了频次这个维度，基础数据结构是桶：Bucket
2）核心思想就和LRU很相似，如果面试遇到的话说核心思想，然后尝试这沟通看看能否写其中一个函数，太复杂了这个玩意。