LRU算法:

LRULeast Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。

基于 哈希表 + 双向链表Java 实现

  • 查找 : 通过哈希表查找到,然后移动到双向链表的头部。
  • 删除 : 通过哈希表查找到,通过双向链表拿到前驱节点,直接删除即可。
  • 插入 : 先看是否存在,如果存在移动到链表头部,如果不存在,链表满的话删除尾节点,然后插入链表尾头部,否则不满,则直接插入链表头部。
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
public class LRUCache {

private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;

head = new DLinkedNode();
head.pre = null;

tail = new DLinkedNode();
tail.post = null;

head.post = tail;
tail.pre = head;
}

public int get(String key) {

DLinkedNode node = cache.get(key);
if(node == null){
return -1; // should raise exception here.
}

// move the accessed node to the head;
this.moveToHead(node);

return node.value;
}


public void set(String key, int value) {
DLinkedNode node = cache.get(key);

if(node == null){

DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;

this.cache.put(key, newNode);
this.addNode(newNode);

++count;

if(count > capacity){
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
this.moveToHead(node);
}
}
/**
* Always add the new node right after head;
*/
private void addNode(DLinkedNode node){
node.pre = head;
node.post = head.post;

head.post.pre = node;
head.post = node;
}

/**
* Remove an existing node from the linked list.
*/
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;

pre.post = post;
post.pre = pre;
}

/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node){
this.removeNode(node);
this.addNode(node);
}

// pop the current tail.
private DLinkedNode popTail(){
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}

class DLinkedNode {
String key;
int value;
DLinkedNode pre;
DLinkedNode post;
}
}

基于 LinkedHashMap的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE;

/**
* 传递进来最多能缓存多少数据
*
* @param cacheSize 缓存大小
*/
public LRUCache(int cacheSize) {
// true 表示让 linkedHashMap 按照访问顺序来进行排序,最近访问的放在头部,最老访问的放在尾部。
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当 map中的数据量大于指定的缓存个数的时候,就自动删除最老的数据。
return size() > CACHE_SIZE;
}
}