LRU（least recently used）
LRU算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
具体过程
- 新数据插入到链表头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
- 当链表满的时候，将链表尾部的数据丢弃。
数据结构
- HashMap：快速搜索的基础
- 双向链表：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
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
| public class SimpleLRU<T> {
int capacity;
private Node<T> head;
private Node<T> tail;
private HashMap<String, Node<T>> map;
private SimpleLRU() {
}
public SimpleLRU(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity);
}
private static class Node<T> {
String key;
T value;
Node<T> next;
Node<T> pre;
private Node() {
}
private Node(String key, T value) {
this.key = key;
this.value = value;
}
}
public T get(String key) {
Node<T> node = map.get(key);
if (node == null) {
return null;
}
if (head == tail) {
return node.value;
}
if (node != head && node != tail) {
Node<T> p = node.pre;
Node<T> q = node.next;
p.next = q;
q.pre = p;
head.pre = node;
node.next = head;
head = node;
} else if (node == tail) {
tail = node.pre;
tail.next = null;
node.next = head;
head.pre = node;
node.pre = null;
head = node;
}
return node.value;
}
public boolean put(String key, T value) {
if (value == null || key.trim().equals("")) {
return false;
}
Node<T> oldNode;
if ((oldNode = map.get(key)) != null) {
oldNode.value = value;
return true;
}
Node<T> newNode = new Node<>(key, value);
if (map.size() >= capacity) {
Node<T> delNode = tail;
String delKey = delNode.key;
map.remove(delKey);
map.put(key, newNode);
if (capacity == 1) {
tail = newNode;
head = newNode;
} else {
Node<T> preNode = tail.pre;
preNode.next = newNode;
}
} else {
map.put(key, newNode);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
return true;
}
}
|
