LRU自定义最近最少使用-java实现

一：leetCode 题目

题目链接：

题目链接：146.LRU缓存

为什么要写博客记录下呢？

1.这个题很锻炼自己的编码能力（代码量多，结构多）
2.这个题很锻炼自己的owner能力（感觉挑战底层类，不屈于写业务代码）
3.这个题很锻炼自己的耐力（调试比较麻烦）
4.这个题很锻炼自己的边界能力（各种边界条件需要测试）

二：思路

1. 最近最少使用：

最近最少使用 翻译下：把最后一个不使用的给踢出去

维护一个队列
使用的放到队列的前头
队尾永远是最近最少使用的

翻译：使用了就放队列前头，想移除就移除队尾

2. 如何实现队列，O(1) 的复杂度

首先想到的是链表，这里使用最普通的 listNode的结构体

class ListNode {
    int val;
    ListNode next;
    ListNode parent;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
        this.parent = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11

三：上代码

代码：

• 类代码
• 测试代码

3.1：类代码

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

	// 初始化的容量
    private final int capacity;

	// 元数据
    private final Map<Integer, Integer> metaMap;

	// 用于记录 key 和队列的关系
    private final Map<Integer, ListNode> metaLinkedMap;

	// 最后一个结点
    private ListNode lastNode;

	// 头结点
    private final ListNode headNode;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        metaMap = new HashMap<>();
        metaLinkedMap = new HashMap<>();
        // 请注意！！！ 这里我太笨了，我这里前两个结点都是头结点。这样有利于我个人的思考 ！！！！！
        ListNode dataNode = new ListNode(0);
        headNode = new ListNode(0);
        headNode.next = dataNode;
    }

    // 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
    public int get(int key) {
        if (metaMap.containsKey(key)) {
            // 调整频率
            adjustExistNodeSort(key);

            return metaMap.get(key);
        }
        return -1;
    }

    // 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字
    public void put(int key, int value) {
        if (metaMap.containsKey(key)) {
            // 更新热点数据
            adjustExistNodeSort(key);

            // 替换数据
            metaMap.put(key, value);
        } else {
            if (metaMap.size() == capacity) {
                // 需要移除数据
                removeLastNode();
            }

            ListNode putNode = new ListNode(key);

            // 更新热点数据
            adjustNewNodeSort(putNode);

            // 初始化信息
            metaMap.put(key, value);
            metaLinkedMap.put(key, putNode);
        }
    }

    /**
     * 排序一个已经存在的结点
     * @param key 已经存在的key
     */
    private void adjustExistNodeSort(Integer key) {
        ListNode hotNode = metaLinkedMap.get(key);
        ListNode oldHeadNode = headNode.next.next;

        if (hotNode == oldHeadNode){
            return;
        }

        hotNode.parent.next = hotNode.next;
        if (hotNode.next != null){
            hotNode.next.parent = hotNode.parent;
        }

        if (lastNode == hotNode && metaMap.size() != 1) {
            lastNode = hotNode.parent;
        }

        if (oldHeadNode != null) {
            oldHeadNode.parent = hotNode;
            hotNode.next = oldHeadNode;
        }
        headNode.next.next = hotNode;
        hotNode.parent = headNode.next;
    }


    /**
     * 调整一个新结点的排序
     * @param putNode 新节点
     */
    private void adjustNewNodeSort(ListNode putNode) {
        // 初始化末尾节点
        if (lastNode == null || metaMap.size() == 0) {
            lastNode = putNode;
        }

        // 放到头节点
        ListNode oldHeadNode = headNode.next.next;

        if (oldHeadNode != null) {
            oldHeadNode.parent = putNode;
            putNode.next = oldHeadNode;
        }

        headNode.next.next = putNode;
        putNode.parent = headNode.next;

    }

    /**
     * 移除最后一个元素
     */
    private void removeLastNode() {
        int lastVal = lastNode.val;
        metaMap.remove(lastVal);
        metaLinkedMap.remove(lastVal);
        lastNode = lastNode.parent;
        lastNode.next = null;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode parent;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
        this.parent = null;
    }
}


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

3.2： 测试代码

import java.util.HashSet;
import java.util.Set;

// Press Shift twice to open the Search Everywhere dialog and type `show whitespaces`,
// then press Enter. You can now see whitespace characters in your code.
public class Main {
    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(1);
        lruCache.get(6);
        lruCache.get(8);

        lruCache.put(12,1);

        lruCache.get(2);

        lruCache.put(15,11);

        lruCache.put(5,2);
        lruCache.put(1,15);
        lruCache.put(4,2);

        lruCache.get(5);
        lruCache.put(15,15);
    }
}
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