1. 常见的缓存淘汰策略
- 先进先出策略 FIFO (First in, First out)
- 最少使用策略 LFU (Least Frequently Used)
- 最近最少使用策略 LRU (Least Recently Used)
2. 怎样实现 LRU 缓存淘汰策略
思路
- 维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表
- 如果此数据之前已经被缓存在链表中，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部
- 如果此数据没有缓存在链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表头部
- 如果此时缓存已满，则删除链表尾结点，将新的数据结点插入链表的头部
基于 Array
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
133import java.util.HashMap;
import java.util.Map;
/**
* 基于数组的 LRU 缓存淘汰算法
* 1. 空间复杂度为 O(n)
* 2. 时间复杂度为 O(n)
* 3. 不支持 null 的缓存
*/
public class LRUBaesArray<T> {
private static final int DEFAULT_CAPACITY = (1 << 3); // TODO
private int capacity;
private int length;
private T[] elements;
private Map<T, Integer> holder;
public LRUBaseArray() {
this(DEFAULT_CAPACITY);
}
public LRUBaseArray(int capacity) {
this.capacity = capacity;
elements = (T[]) new Object[capacity];
length = 0;
holder = new HashMap<T, Integer> (capacity);
}
// 模拟访问某个值
public void offer(T object) {
if(object == null) {
throw new IllegalArgumentException("该缓存容器暂不支持 null");
}
Integer index = holder.get(objcet);
if(index == null) {
if(isFull()) {
removeAndCache(object);
} else {
cache(object, length);
}
} else {
update(index);
}
}
// 若缓存中有指定的值，则更新位置
public void update(int end) {
T target = elements[end];
rightShift(end);
elements[0] = target;
holder.put(target, 0);
}
// 先右移，然后缓存数据到头部
public void cache(T object, int end) {
rightShift(end);
elements[0] = object;
holder.put(object, 0);
length++;
}
// 缓存满的情况，先删除，再缓存到数组头部
public void removeAndCache(T object) {
T key = elements[--length];
holder.remove(key);
cache(object, length);
}
// end 左边的数据统一右移一位
private void rightShift(int end) {
for(int i = end - 1; i >= 0; i--) {
elements[i + 1] = elements[i];
holder.put(value[i], i + 1);
}
}
public boolean isContain(T object) {
return holder.containsKey(object);
}
public boolean isEmpty() {
return length == 0;
}
public boolean isFull() {
return length == capacity;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for(int i=0; i < length; i++) {
sb.append(elements[i]);
sb.append(" ");
}
return sb.toString();
}
static class TestLRUBaseArray {
public static void main(String[] args) {
testDefaultConstructor();
testSpecifiedConstructor(4);
// testWithException();
}
private static void testWithException() {
LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
lru.offer(null);
}
public static void testDefaultConstructor() {
System.out.println("======无参测试======");
LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
for(int i=1; i <= 5; i++) {
lru.offer(i);
}
System.out.println(lru);
for(int i=6; i <= 9; i++) {
lru.offer(i);
}
System.out.println(lru);
}
public static void testSpecifiedConstructor(int capacity) {
System.out.println("======有参测试======");
LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> (capacity);
for(int i=1; i <= 9; i++) {
lru.offer(i);
System.out.println(lru);
}
}
}
}基于 LinkedList
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
135import java.util.Scanner;
/**
* 基于单链表的 LRU 缓存淘汰算法
*/
public class LRUBaseLinkedList<T> {
private static final Integer DEFAULT_CAPACITY = 10; // 默认链表容量
private Node<T> headNode; // 头结点
private Integer length; // 链表长度
private Integer capacity; // 链表容量
public LRUBaseLinkedList() {
this.headNode = new Node<> ();
this.capacity = DEFAULT_CAPACITY;
this.length = 0;
}
public LRUBaseLinkedList(Integer capacity) {
this.headNode = new Node<> ();
this.capacity = capacity;
this.length = 0;
}
public void add(T element) {
Node preNode = findPreNode(element);
if(preNode != null) { // 链表中存在，删除原数据，再插入到链表的头部
deleteNextElemAt(preNode);
insertElemAtBegin(element);
} else {
if(length >= this.capacity) {
deleteElemAtEnd(); // 删除尾结点
}
insertElemAtBegin(element);
}
}
// 删除 preNode 的下一个结点
private void deleteNextElemAt(Node preNode) {
Node temp = preNode.getNext();
preNode.setNext(temp.getNext());
temp = null;
length--;
}
// 在链表头部插入结点
private void insertElemAtBegin(T element) {
Node next = head.getNext();
headNode.setNext(new Node(element, next));
length++;
}
// 获取参数结点的前一个结点
private Node findPreNode(T element) {
Node node = headNode;
while(node.getNext() != null) {
if(element.equals(node.getNext().getElement())) {
return node;
}
node = node.getNext();
}
return null;
}
// 删除尾结点
private void deleteElemAtEnd() {
Node node = headNode;
// 空链表直接返回
if(node.getNext() == null) {
return;
}
// 定位到倒数第二个结点
while(node.getNext().getNext() != null) {
node = node.getNext();
}
Node temp = node.getNext();
node.setNext(null);
temp = null;
length--;
}
private void printAll() {
Node node = headNode.getNext();
while(node != null) {
System.out.print(node.getElement() + ", ");
node = node.getNext();
}
System.out.println();
}
public class Node<T> {
private T element;
private Node next;
public Node() {
this.next = null;
}
public Node(T element) {
this.element = element;
}
public Node(T element, Node next) {
this.element = element;
this.next = next;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public static void main(String[] args) {
LRUBaseLinkedList list = new LRUBaseLinkedList();
Scanner in = new Scanner(System.in);
while(true) {
list.add(in.nextInt());
list.printAll();
}
}
}基于 LinkedHashMap
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// 参考站内博客：《Java Map 和 Set （六）：剖析 LinkedHashMap》之问题 11
public class LRUBaseLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private int maxEntries;
// 在构造方法中传递一个容量限制
public LRUBaseLinkedHashMap(int maxEntries) {
super(16, 0.75f, true);
this.maxEntryies = maxEntries;
}
@Override
protected boolean removeEldestEntry(Entry<K, V> eldest) {
return size() > maxEntries;
}
}
// 使用这个缓存容器
LRUBaseLinkedHashMap<String, Object> cache = new LRUBaseLinkedHashMap<> (3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.put("a");
cache.put("d", "call");
System.out.print(cache);
// 因为限定缓存容量为 3， 这里先后添加了 4 个键值对
// 最久没被访问（最近最少使用）的键是 b，会被删除。所以，输出为：{c=call a=abstract, d=call}
3. 如果字符串是通过单链表存储的，怎样判断给定字符串是不是回文字符串
1 | // TODO: confirmed it by Zheng |