LeetCode刷题笔记 —— 146 LRU的实现

题目解析：

设计一个LRU缓存，规定好最大容量，设计get/put接口，当即将超出容量的时候，要把最久未使用的缓存删除

最久未使用：最久没有进行 get/put操作

要求get/put均为o(1)复杂度

o(1)的key value，必然是哈希表，可是应该怎么获取 最久未使用 这一个信息？

第一思路：把 最久未获取 当成一个属性来维护

最久未使用 这一信息的获取过程，是伴随着 put 操作发生的，因此，put想要是O(1)，获取最久未使用也必须是O(1)

换句话说，我们想要这个信息的获取既能和key的获取一样便捷，又能把他和key联系起来

然而，哈希表也仅有key能在O(1)时间内获取，getvalue则是通过遍历哈希key获得的，时间复杂度是O(n)

同样的道理，使用 栈 Stack 来维护这个信息，在移除头节点的时候，remove(0)操作也是需要O(n)的时间

**第二思路：1. 利用某种数据结构的特性，把时间信息隐含到数据结构里 **

​ **2.必须满足通过key查找到它的过程不是O(n)遍历，而是直接得到 **

因此我们使用 双向链表 作为数据结构，因为双向链表可以在O(1)的复杂度内，完成节点的拆除，移位等，保证了 操作的过程不用去遍历

但是，还有一个很大的问题，就是如果我们的哈希表是 key value，在双向链表中存的信息是key，那我们可以很轻松的通过节点拿到key，但反过来就不行了，也就是没有满足第二条，必须满足通过key查找到它的过程不是O(n)遍历

既然我们已经自定义节点了，节点能存什么，我们是完全能控制的，所以，为啥一定要让链表作为map的小弟，去只给他存key呢？

因此，我们可以做以下改进：

  1. 让节点存 key ，value
  2. 不让map存value了，我们缓存的主体是链表，map只用来进行唯一性判断和大小统计，所以，map的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

class LRUCache {

    HashMap <Integer,Node> cacheMap;
    //定义头尾节点，用起来更爽
    Node head;
    Node tail;
    int capacity;
    public LRUCache(int capacity) {
        head = new Node();
        tail = new Node();
        head.setNext(tail);
        tail.setPre(head);
        this.capacity = capacity;
        cacheMap = new HashMap();
    }
    
    public int get(int key) {
        //判断是否存在
        if(cacheMap.containsKey(key)){
            Node tempNode = cacheMap.get(key);
            tempNode.getPre().setNext(tempNode.getNext());
            tempNode.getNext().setPre(tempNode.getPre());

            tempNode.setNext(tail);
            tempNode.setPre(tail.getPre());
            tempNode.getPre().setNext(tempNode);
            tail.setPre(tempNode);

            return tempNode.getValue();
        }
        //不存在，返回-1
        return -1;
    }
    
    public void put(int key, int value) {
        //1.判断key是否存在
        Boolean keyExists = cacheMap.containsKey(key);
        //2.不存在的话
        if(!keyExists){
            //2.1如果已经满了,先删一个
            if(cacheMap.size()==capacity){
                Node delNode = head.getNext();
                head.setNext(delNode.getNext());
                delNode.getNext().setPre(head);
                int delKey = delNode.getKey();
                delNode = null;//暗示gc把他删了
                cacheMap.remove(delKey);
            }
            //2.2新建node，存入value，存到tail前面
            Node newNode = new Node();
            newNode.setValue(value);
            newNode.setKey(key);
            newNode.setPre(tail.getPre());
            newNode.setNext(tail);
            newNode.getPre().setNext(newNode);
            tail.setPre(newNode);
            cacheMap.put(key,newNode);
        }else{
        //3.0存在的话
        //3.1找到节点，更新value，拆出来，放在tail前面
            Node changeNode = cacheMap.get(key);

            changeNode.getPre().setNext(changeNode.getNext());
            changeNode.getNext().setPre(changeNode.getPre());

            changeNode.setNext(tail);
            changeNode.setPre(tail.getPre());
            changeNode.setValue(value);
            tail.getPre().setNext(changeNode);
            tail.setPre(changeNode);
        }

        
    }
}


public class Node{
    private Node preNode;
    private Node nextNode;

    //这里是关键，我们不是拿着key来双向链表里面找Node，而是hash里面不存value，而是存双向链表的节点，value直接存在节点里

    private int value;
    private int key;

    public Node getPre(){
        return preNode;
    }

    public Node getNext(){
        return nextNode;
    }

    public void setPre(Node preNode){
        this.preNode = preNode;
    }

    public void setNext(Node nextNode){
        this.nextNode = nextNode;
    }

    public int getValue(){
        return value;
    }
    public void setValue(int value){
        this.value = value;
    }
    public int getKey(){
        return key;
    }

    public void setKey(int key){
        this.key = key;
    }

}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */