146. LRU 缓存 - 力扣（LeetCode）
算法就像搭乐高：带你手撸 LRU 算法 :: labuladong的算法小抄
LRU , Least Recently Used 按照访问数据的访问频率来进行操作, 在缓存写满的时候，会根据所有数据的访问记录，淘汰掉未来被访问几率最低的数据 , 在os中的页面置换算法以及MySQL 的innodb存储引擎 ( MySQL中的具体参数有所改变 , 不过算法思想是相通的 )中都有使用 , 因此熟悉LRU的具体操作还是十分必要的 。
LRU算法认为，最近被访问过的数据，在将来被访问的几率最大。
算法实现
HashMap + 双向链表
1
| transient Node<K,V>[] table;
|
关于java 中transient 关键字 , 首先我们知 道如果一个类实现了Serilizable 接口并且声明了 Serializable, 那么这个类就可以被序列化 , 那么 transient 的作用就是用于标记类中的属性, ==表示这个属性不会被序列化==
我们知道java中的HashMap 类的底层实现是使用数组实现的 , 如果出现了哈希冲突 , 在java8以前会使用链表扩容, java8以及以后使用的是红黑树进行扩容 , 但是如果在当前的场景中, 由于HashMap是无序的, 因此我们无法获取到哪个是 最久没有使用的数据 , 这个时候就需要借助于链表 , 我们维持一个序列 , 把每次使用的数据以及添加的数据添加到序列的尾部 , 如果在添加的时候发现 序列达到了最大的容量 , 就删除最前面的数据 , 这样也就达到了 Least Recently Used 的要求, 由于时间复杂度方面的要求 , 需要使用双向链表实现 , 但是由于链表获取数据的时间复杂度为 O(N) , 因此需要通过hash来快速的进行查找
自然而然, Map的映射关系为 index: Node , 对应 java中的数据类型也就是 <Integer, Node> , 下面为具体的代码实现
手写双向链表 , 然后通过HashMap以及 DoubleList 来实现 LRUCache
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
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
| class LRUCache {
int capacity;
Map<Integer,Node> map;
DoubleList cache;
public LRUCache(int capacity) {
cache=new DoubleList();
map=new HashMap<>();
this.capacity=capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
makeRecently(key);
return map.get(key).val;
}
public void put(int key, int val) {
if(map.containsKey(key)){
deleteKey(key);
addRecently(key, val);
return;
}
if(cache.size==capacity){
removeLeastRecently();
}
addRecently(key,val);
}
private void deleteKey(int key){
Node node = map.get(key);
cache.remove(node);
map.remove(key);
}
private void removeLeastRecently(){
Node node = cache.removeFirst();
map.remove(node.key);
}
private void makeRecently(int key){
Node node = map.get(key);
cache.remove(node);
cache.addLast(node);
}
private void addRecently(int key,int val){
Node node =new Node(key,val);
cache.addLast(node);
map.put(key,node);
}
class Node{
int key,val;
Node pre,next;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
class DoubleList{
Node head,tail;
int size;
public DoubleList(){
head=new Node(0,0);
tail=new Node(0,0);
head.next=tail;
tail.pre=head;
size=0;
}
public void remove(Node x){
x.pre.next= x.next;
x.next.pre=x.pre;
size--;
}
public int size(){
return size;
}
public Node removeFirst(){
if(head.next==tail) return null;
Node res=head.next;
remove(res);
return res;
}
public void addLast(Node node){
node.pre=tail.pre;
node.next=tail;
tail.pre.next=node;
tail.pre=node;
size++;
}
}
}
|
LinkedHashMap
而实际上java中已经有了类似功能的类 , 那么我们也可以直接使用 LinkedHashMap 来进行操作 , 具体原理不再赘述 , 可以参考
LinkedHashMap 源码
1
2
3
4
5
6
| static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
|
使用LinkedHashMap 实现LRU
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
| class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
cache.put(key, val);
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
cache.remove(key);
cache.put(key, val);
}
}
|
简单测试
设置好capacity , 然后进行添加即可
1
2
3
4
5
6
7
8
9
10
| public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
System.out.println("the first Node :"+cache.get(1));
cache.put(4, 3);
System.out.println(cache);
}
|
打印结果为
1
2
| the first Node :1
LRUCache{values={1=Node{key=1, val=1}, 3=Node{key=3, val=3}, 4=Node{key=4, val=3}}}
|
