最不经常使用LFU（least frequently used）算法java实现_最不经常使用算法

• 最不经常使用LFU（least frequently used）算法java实现
  • 一.手撸 LFU 算法实现（Hash表 + 双向链表）
  • 二.总结

最不经常使用LFU（least frequently used）算法java实现

LFU（least frequently used (LFU) page-replacement algorithm）。即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。

以上是来自百度百科的介绍，通俗来说，LFU 就是一个淘汰算法，例如内存相较于硬盘可以快速的读写，但是内存的空间是有限的，为了有效的利用内存空间，就需要将一些非热点数据给淘汰掉，这里就用到 LFU 算法，它会将内存中最不经常使用的数据给淘汰掉。

LFU 算是 LRU（Least Recently Used） 的一种变种算法，LRU 算法在找工作面试中，经常会被问到，需要能够在短时间内写出来，大家平时还是要勤加练习。

LRU 算法的 java 算法实现请参见我另一篇博文：最近最少使用LRU（Least Recently Used）算法java实现

动动发财小手，关注 + 点赞 + 收藏不迷路。

一.手撸 LFU 算法实现（Hash表 + 双向链表）

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * LFU (Least frequently used)最不经常使用
 *
 * @Date: 2022/01/07 10:10
 */
public class LfuCache {

    private static ConcurrentHashMap<String, ListNode> cacheMap;

    private static AtomicInteger count;

    private static int capacity;

    private final ListNode head = new ListNode();

    private final ListNode tail = new ListNode();

    LfuCache(int capacity) {
        count = new AtomicInteger(0);
        LfuCache.capacity = capacity;
        cacheMap = new ConcurrentHashMap<>();
        this.tail.pre = head;
        this.head.next = tail;
    }

    private static class ListNode {

        ListNode() {
        }

        ListNode(String key) {
            this.key = key;
            this.count = 1;
        }

        private String key;

        private int count;

        private ListNode pre;

        private ListNode next;

        public String getKey() {
            return this.key;
        }

    }

    public void put(ListNode node) {
        ListNode existNode = get(node);
        if (existNode != null) {
            // cacheMap中node存在,先remove节点,再把节点移到链表头部
            existNode.count++;
            ListNode replaceNode = existNode.pre;
            while (replaceNode != head && replaceNode.count < existNode.count) {
                replaceNode = replaceNode.pre;
            }
            if (replaceNode == head) {
                removeNode(existNode);
                headAdd(existNode);
            }
            // 即：replaceNode.count >= existNode.count，在链表中移除existNode，并移动到replaceNode的后面
            replaceNode = replaceNode.next;
            if (replaceNode != tail && replaceNode != existNode) {
                removeNode(existNode);
                existNode.next = replaceNode;
                existNode.pre = replaceNode.pre;
                replaceNode.pre.next = existNode;
                replaceNode.pre = existNode;
            }
        } else {
            // cacheMap中node不存在,插入
            if (count.get() == capacity) {
                tailRemove();
                // count--
                count.decrementAndGet();
            }
            tailAdd(node);
            // count++
            count.incrementAndGet();
            cacheMap.put(node.getKey(), node);
        }
    }

    public void headAdd(ListNode node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    public void tailAdd(ListNode node) {
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    public void removeNode(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void tailRemove() {
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
    }

    public ListNode get(ListNode node) {
        return cacheMap.get(node.getKey());
    }

    public void print() {
        ListNode node = head;
        System.out.println("============================================");
        while (node.next != null && node.next != tail) {
            System.out.println(node.next.key + ", key count = " + node.next.count + ", LruCache count = " + count);
            node = node.next;
        }
    }

    public void print(String key) {
        ListNode node = head;
        System.out.println("================  put " + key + "  ================");
        while (node.next != null && node.next != tail) {
            System.out.println(node.next.key + ", key count = " + node.next.count + ", LruCache count = " + count);
            node = node.next;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode("1");
        ListNode node2 = new ListNode("2");
        ListNode node3 = new ListNode("3");
        ListNode node4 = new ListNode("4");
        LfuCache lruCache1 = new LfuCache(3);
        lruCache1.put(node1);
        lruCache1.print();
        lruCache1.put(node2);
        lruCache1.print();
        lruCache1.put(node3);
        lruCache1.print();
        lruCache1.put(node4);
        lruCache1.print();

        System.out.println("");
        System.out.println("###################################################");
        System.out.println("");

        ListNode node9 = new ListNode("9");
        LfuCache lruCache2 = new LfuCache(3);
        lruCache2.put(node9);
        lruCache2.print();
        lruCache2.put(node9);
        lruCache2.print();

        System.out.println("");
        System.out.println("###################################################");
        System.out.println("");

        ListNode node5 = new ListNode("5");
        ListNode node6 = new ListNode("6");
        ListNode node7 = new ListNode("7");
        ListNode node8 = new ListNode("8");
        LfuCache lruCache3 = new LfuCache(4);
        lruCache3.put(node5);
        lruCache3.print("5");
        lruCache3.put(node6);
        lruCache3.print("6");
        lruCache3.put(node7);
        lruCache3.print("7");
        lruCache3.put(node5);
        lruCache3.print("5");
        lruCache3.put(node5);
        lruCache3.print("5");
        lruCache3.put(node8);
        lruCache3.print("8");
        lruCache3.put(node8);
        lruCache3.print("8");

        System.out.println("");
        System.out.println("###################################################");
        System.out.println("");

        ListNode node10 = new ListNode("10");
        ListNode node11 = new ListNode("11");
        ListNode node12 = new ListNode("12");
        ListNode node13 = new ListNode("13");
        LfuCache lruCache4 = new LfuCache(3);
        lruCache4.put(node10);
        lruCache4.put(node10);
        lruCache4.put(node10);
        lruCache4.print();
        lruCache4.put(node11);
        lruCache4.print();
        lruCache4.put(node12);
        lruCache4.put(node12);
        lruCache4.print();
        lruCache4.put(node13);
        lruCache4.print();
    }

}

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

输出如下：

============================================
1, key count = 1, LruCache count = 1
============================================
1, key count = 1, LruCache count = 2
2, key count = 1, LruCache count = 2
============================================
1, key count = 1, LruCache count = 3
2, key count = 1, LruCache count = 3
3, key count = 1, LruCache count = 3
============================================
1, key count = 1, LruCache count = 3
2, key count = 1, LruCache count = 3
4, key count = 1, LruCache count = 3

###################################################

============================================
9, key count = 1, LruCache count = 1
============================================
9, key count = 2, LruCache count = 1

###################################################

================  put 5  ================
5, key count = 1, LruCache count = 1
================  put 6  ================
5, key count = 1, LruCache count = 2
6, key count = 1, LruCache count = 2
================  put 7  ================
5, key count = 1, LruCache count = 3
6, key count = 1, LruCache count = 3
7, key count = 1, LruCache count = 3
================  put 5  ================
5, key count = 2, LruCache count = 3
6, key count = 1, LruCache count = 3
7, key count = 1, LruCache count = 3
================  put 5  ================
5, key count = 3, LruCache count = 3
6, key count = 1, LruCache count = 3
7, key count = 1, LruCache count = 3
================  put 8  ================
5, key count = 3, LruCache count = 4
6, key count = 1, LruCache count = 4
7, key count = 1, LruCache count = 4
8, key count = 1, LruCache count = 4
================  put 8  ================
5, key count = 3, LruCache count = 4
8, key count = 2, LruCache count = 4
6, key count = 1, LruCache count = 4
7, key count = 1, LruCache count = 4

###################################################

============================================
10, key count = 3, LruCache count = 1
============================================
10, key count = 3, LruCache count = 2
11, key count = 1, LruCache count = 2
============================================
10, key count = 3, LruCache count = 3
12, key count = 2, LruCache count = 3
11, key count = 1, LruCache count = 3
============================================
10, key count = 3, LruCache count = 3
12, key count = 2, LruCache count = 3
13, key count = 1, LruCache count = 3

Process finished with exit code 0
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

二.总结

本文是在 最近最少使用LRU（Least Recently Used）算法java实现 基础上的变种算法，有兴趣的可以参考一下。