不能再等啦，手撕LRU、LFU，今天你必须学会！！！ 分享大

发表于

「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」

前言

就目前情况而言，只要你简历上敢写Redis，大厂面试官就一定敢叫你手写LRU，但对于手写LFU相对而言还是比较少见，但如果，你写完LRU还能对面试官说你还掌握LFU算法，那么即使你写不出来只说出个大概，那么在面试官心中也是大大加分的！！！

那么，今天就让我来帮助大家掌握这个高频考点吧！！！

==温馨提示==：主要理解思路在注释中
注释有点浅，大家可以复制到自己的编译器中好好看看

大厂面试题专栏，里面有更多更优质的大厂面试题，可以来看一看瞅一瞅哦！！！

手撕LRU

LRU总体上还是比较简单的，只要你掌握概念，即使长时间没写也还能记得！

LRU总体上思路：最近使用的放在最近的位置（最左边），那么保证了这个最少使用的就自然而然离你远了（往右边去了）

所以说使用双向链表来实现，但光有这还不够，我们还需要使用Map来将key映射到对应的节点

在双向链表中，使用虚拟头节点和尾节点来作为节点，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

在这里插入图片描述

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
java复制代码public class Main {


	//定义双向链表
    class DoubleLinkedList {
        private int key;
        private int value;
        private DoubleLinkedList next;
        private DoubleLinkedList prev;

        public DoubleLinkedList() {
        }

        public DoubleLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


	//虚拟头节点，尾节点
    private DoubleLinkedList head,tail;
    //存放映射的HashMap
    private Map<Integer,DoubleLinkedList> map = new HashMap<>();
    //容量
    private int capacity;
    //实际元素个数
    private int size;

	//数据初始化
    public Main(int capacity) {
        this.capacity = capacity;
        head = new DoubleLinkedList();
        tail = new DoubleLinkedList();
        head.next = tail;
        tail.prev = head;
        this.map = new HashMap<>();
    }

	//对外暴露的get方法
    public int get(int key) {
    	//如果不存在key，则返回-1
        if (!map.containsKey(key)) {
            return -1;
        }
        //来到这，说明有这个key，那么就给put出来
        DoubleLinkedList node = map.get(key);
		
		//因为使用过了该节点，那么就需要将其移动到头节点
        moveToHead(node);
		//返回value值
        return node.value;
    }

	//对外暴露的put方法
    public void put(int key,int value) {
        
        //如果存在该key
        if (map.containsKey(key)) {
        	//那么get出来，替换value值，因为使用过，所以移动到头节点
            DoubleLinkedList node = map.get(key);
            node.value = value;
            moveToHead(node);
        }else {
			//因为不存在该key
			//所以创建新的节点
            DoubleLinkedList newNode = new DoubleLinkedList(key, value);
			
			//将节点加入到map中去，并将其添加到头节点，元素总数量加1
            map.put(key,newNode);
            addHead(newNode);
            size++;
            
			//如果元素总数量大于最大容量
            if (size > capacity) {
            	//那么删除最后一个节点，也就是最少使用的节点
                removeLastNode();
            }
        }
    }

	//删除末尾节点
    private void removeLastNode() {
    	//tail为虚拟尾节点，所以它前面的节点就是最后一个节点
        DoubleLinkedList lastNode = tail.prev;
        
        //删除节点
        removeNode(lastNode);
        map.remove(lastNode.key);
        size--;
    }

	//移动节点到头节点
    private void moveToHead(DoubleLinkedList node) {
        removeNode(node);
        addHead(node);
    }

	//添加节点到头节点
    private void addHead(DoubleLinkedList node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

	//删除节点
    private void removeNode(DoubleLinkedList node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = null;
    }

}

力扣：LRU地址

手撕LFU

LFU就不像是LFU那样根据最近使用之类的来编排
LFU是根据使用的频次，简单来说是根据使用的次数来编排（在保证次数的情况下，根据最近使用来排），所以对于链表节点需要多定义一个使用的次数count

在这里插入图片描述

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
java复制代码public class Main {


	//定义链表
    class Node {
        private int key;
        private int value;
        private int count;
        private Node next;
        private Node prev;

        public Node() {
        }

        public Node(int key, int value,int count) {
            this.key = key;
            this.value = value;
            this.count = count;
        }
    }


	//key与对应的Node节点映射
    private Map<Integer,Node> keyMap;
    //频次与其对应区域首节点的映射
    private Map<Integer,Node> cntMap;
    //虚拟头节点、尾节点
    private Node head,tail;
	//最大容量
    private int capacity;
    //元素实际个数
    private int size;


	//初始化
    public Main(int capacity) {
        this.capacity = capacity;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
        keyMap = new HashMap<>();
        cntMap = new HashMap<>();
    }


	//对外暴露get方法
    public int get(int key) {
    	//容量为0，或者不存在key则返回-1
        if (capacity == 0 || !keyMap.containsKey(key)) {
            return -1;
        }
        //去除key对应的节点
        Node node = keyMap.get(key);

		//更新使用频次
        updateNode_fre(node);
		//返回value
        return node.value;
    }

	//更新节点使用频次
    private void updateNode_fre(Node node) {
		//旧的使用频次
        int oldCnt = node.count;
        //新的使用频次
        int newCnt = node.count + 1;

		//需要保存在哪个节点前插入的
		//因为插入的位置可能是区域的首节点，也可能不是
        Node next = null;

		//如果当前节点是该使用频次的首节点
        if (cntMap.get(oldCnt) == node) {
        
        	//如果当前区域还有下一个节点，那么直接把当前区域的首节点设置为下一节点就好了
            if (node.next.count == node.count) {
                cntMap.put(oldCnt,node.next);
            }else {
            	//如果没有下一个节点了，那么就需要删除此区域了。因为该节点频次要更新了
                cntMap.remove(oldCnt);
            }
			
			//如果不存在新区域
            if (cntMap.get(newCnt) == null) {
            	//那么创建新区域，并将该节点设置为首节点
                cntMap.put(newCnt,node);
                //频次要更新
                node.count++;
                //不需要后续操作了
                return;
            }else {
            	//如果存在，那么就需要删除该节点，将next设置为新区域首节点
                removeNode(node);
                next = cntMap.get(newCnt);
            }
        }else {
        	//如果不是，那么删除节点
            removeNode(node);
            //如果存在新使用频次的区域则 next就等于新使用区域频次的首节点
            //如果没有，那么在当前使用频次前面插入就ok了
            if (cntMap.get(newCnt) == null) {
                next = cntMap.get(oldCnt);
            }else {
                next = cntMap.get(newCnt);
            }
        }

		//能来到这的node，频次都是没有更新的，所以更新频次
        node.count++;
        //更新频次映射
        cntMap.put(newCnt,node);
        //在指定节点前插入
        addNode(node,next);
    }


	//对外暴露put方法
    public void put(int key,int value) {
    	//如果容量为0，则不能put键值对
        if (capacity == 0) return;

		//如果存在key
        if (keyMap.containsKey(key)) {
        	//取出节点，替换value，更新
            Node node = keyMap.get(key);
            node.value = value;
            updateNode_fre(node);
        }else {
	
			//如果元素个数等于了最大容量
            if (size == capacity) {
            	//那么就需要删除莫尾节点
                deleteLastNode();
            }

			//创建新节点，默认使用次数为1
            Node newNode = new Node(key, value,1);
            //因为是新节点，所以插入到count=1区域的首部
            Node next = cntMap.get(1);
            //但如果没有这个区域，那么直接插入到
            if (next == null) {
                next = tail;
            }
			
			//插入、更新
            addNode(newNode,next);
            keyMap.put(key,newNode);
            cntMap.put(1,newNode);
            size++;
        }
    }

	//添加节点
    private void addNode(Node node, Node next) {
        node.next = next;
        node.prev = next.prev;
        next.prev.next = node;
        next.prev = node;
    }

	//删除末尾节点
    private void deleteLastNode() {
        Node lastNode = tail.prev;
        //如果该节点是此区域的唯一一个节点，那么需要将此区域删除
        if (cntMap.get(lastNode.count) == lastNode) {
            cntMap.remove(lastNode.count);
        }
        removeNode(lastNode);
        keyMap.remove(lastNode.key);
        size--;
    }

	//删除节点
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.next = null;
        node.prev = null;
    }

}

力扣：LFU地址

最后

我是 Code皮皮虾，一个热爱分享知识的 皮皮虾爱好者，未来的日子里会不断更新出对大家有益的博文，期待大家的关注！！！

创作不易，如果这篇博文对各位有帮助，希望各位小伙伴可以==一键三连哦！==，感谢支持，我们下次再见~

分享大纲

大厂面试题专栏

在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%