题目
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 / 缓存容量 / );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
原题地址 https://leetcode-cn.com/problems/lru-cache
解题思路
思路1
使用linkedhashmap实现，问题在于初始大小小于16，默认会用16，后面的大小是2^n,需要自己控制大小，
容量超过最大，需要用迭代取最老的值删除
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
| class LRUCache {
private LinkedHashMap<Integer,Integer> map;
private int capacity;
public LRUCache(int capacity) {
map = new LinkedHashMap<Integer,Integer>(capacity,0.75f,true);
this.capacity = capacity;
}
public int get(int key) {
Integer value = map.get(key);
if(value == null){
return -1;
}else{
return value;
}
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.remove(key);
}
if(map.size() >= capacity){
map.remove(map.keySet().iterator().next());
}
map.put(key,value);
}
}
|
思路2
哈希表+双向链表
一个hashmap存储key，快速访问，capacity容量记录大小，一个head，tail指针用于添加和删除。
注意点：
- hashmap是key+Node，不然取不出node。
- get方法
- 空表处理
- 存在就删除这个结点，放到head上，要判断head和tail为空的情况
- put
- 小于容量，看是否存在，存在删除，直接放在head
- 等于容量，看是否存在，存在删除，直接放在head
- 不存在，删除tail，放在head
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
| class LRUCache {
private int capacity;
private Map<Integer,Node> map;
private Node head;
private Node tail;
class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
map = new HashMap<Integer,Node>();
this.capacity = capacity;
}
public int get(int key) {
//空表处理
Node node = map.get(key);
if(node == null){
return -1;
}
//存在就删除这个结点，放到head上，要判断head和tail为空的情况
removeNode(node);
insertHead(node);
return node.value;
}
private void removeNode(Node node){
//存在就删除这个结点，放到head上，要判断head和tail为空的情况
Node pre = node.pre;
Node next = node.next;
if(node == tail && node == head){
head = tail = null;
}else if(node == tail){
pre.next = null;
tail = pre;
}else if(node == head){
next.pre = null;
head = next;
}else{
pre.next = next;
next.pre = pre;
}
map.remove(node.key);
}
private void insertHead(Node node){
//插入头部要判断head的空问题
if(head == null){
head = node;
tail = node;
}else{
Node oldHead = head;
node.next = oldHead;
oldHead.pre = node;
head = node;
}
map.put(node.key,node);
}
private void removeTail(){
if(tail == null){
return;
}
map.remove(tail.key);
if(tail.pre == null){
tail = head = null;
}else{
tail = tail.pre;
tail.next = null;
}
}
public void put(int key, int value) {
Node node = map.get(key);
if(map.size() < capacity){
if(node != null){
removeNode(node);
}
Node newNode = new Node(key,value);
insertHead(newNode);
map.put(key,newNode);
}else if(map.size() == capacity){
if(node != null){
removeNode(node);
insertHead(new Node(key,value));
}else{
removeTail();
Node newNode = new Node(key,value);
insertHead(newNode);
}
}
//小于容量，看是否存在，存在删除，直接放在head
//等于容量，看是否存在，存在删除，直接放在head
//不存在，删除tail，放在head
}
}
|
曾经错误点
1.头尾都是一个结点删除结点错误
思路3
哈希表，+带前后哨兵的双向链表，为了简化头尾空的判断。思路2的主要容易错的点是头尾空的情况，那是不是可以用哨兵简化判断，都头尾都是空的结点，没有实际值就不会出现判断空值的特殊情况。
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
| class LRUCache {
private int capacity;
private Map<Integer,Node> map;
//dummy
private Node head;
private Node tail;
class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key, int value){
this.key = key;
this.value = value;
}
public Node(){
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<Integer,Node>();
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = map.get(key);
if(node == null){
return -1;
}
removeNode(node);
insertHeadNode(node);
return node.value;
}
public void put(int key, int value) {
int size = map.size();
Node node = map.get(key);
if(node == null){
if(size == capacity){
removeTail();
}
}else{
removeNode(node);
}
Node newNode = new Node(key,value);
insertHeadNode(newNode);
}
private void removeTail(){
Node preNode = tail.pre;
if(preNode == head){
return;
}
Node node = preNode.pre;
node.next = tail;
tail.pre = node;
map.remove(preNode.key);
}
private void removeNode(Node node){
Node pre = node.pre;
Node next = node.next;
map.remove(node.key);
pre.next = next;
next.pre = pre;
}
private void insertHeadNode(Node node){
Node oldNext = head.next;
node.next = oldNext;
head.next = node;
node.pre = head;
oldNext.pre = node;
map.put(node.key,node);
}
}
|
曾经错误点
1.在put方法内，已经存在的值，重新put的时候，出现了错误，这个时候，不管容量是不是达到最大，也都是要删除该结点重新插入。这个很难发现，测试用例是30上的那个发现的，我几乎不能人力复现，测试用例真的很重要，要是我自己构建测试用例，估计很难发现这个问题。这也是我一直缺失的质量问题。
总结
可以效仿linkedHashmap去实现，它已经预设了实现lru的方法，使用双线链表方便删除与添加，使用hashmap快速查找是否存储，时间复杂度是O（1），空间复杂度是O（n），双向链表和hash表还是比较耗费空间的，但也在允许范围内。哨兵可以简化头尾的判断，减少空值的情况，但会多耗费2个空间。
