LRUCache

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高” 。

搜狗截图20190316173426

代码:

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
/**
* @Author: cuzz
* @Date: 2019/3/16 15:35
* @Description: LRU cache
*/
public class LRUCache {

private Map<Integer, DLinkedList> cache = new HashMap<>();
private int count;
private int capacity;
private DLinkedList head, tail;

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

this.head = new DLinkedList();
this.tail = new DLinkedList();

head.next = tail;
tail.pre = head;
}

public int get(int key) {
DLinkedList node = cache.get(key);
if (node == null) {
return -1;
}
removeNode(node);
addHead(node);
return node.value;
}

public void put(int key, int value) {
DLinkedList node = cache.get(key);
if (node == null) {
node = new DLinkedList(key, value);
addHead(node);
cache.put(key, node);
count++;
if (count > capacity) {
DLinkedList preTail = tail.pre;
removeNode(preTail);
cache.remove(preTail.key);
count--;
}
} else {
node.value = value;
removeNode(node);
addHead(node);
}

}

// 移除给定的结点
private void removeNode(DLinkedList node) {
DLinkedList pre = node.pre;
DLinkedList next = node.next;
pre.next = next;
next.pre = pre;
}

// 把结点添加头节点
private void addHead(DLinkedList node) {
DLinkedList next = head.next;
head.next = node;
node.next = next;
next.pre = node;
node.pre = head;
}

public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 返回 1
cache.put(3, 3); // 使 2 作废
System.out.println(cache.get(2)); // 返回 -1
cache.put(4, 4); // 使 1 作废
System.out.println(cache.get(1)); // 返回 -1 未找到
System.out.println(cache.get(3)); // 返回 3
System.out.println(cache.get(4)); // 返回 4
}

}

class DLinkedList {
int key;
int value;
DLinkedList pre;
DLinkedList next;

public DLinkedList() {};

public DLinkedList(int key, int value) {
this.key = key;
this.value = value;
}
}
-------------本文结束感谢您的阅读-------------

本文标题:LRUCache

文章作者:cuzz

发布时间:2019年03月16日 - 22:03

最后更新:2019年05月16日 - 11:05

原始链接:http://blog.cuzz.site/2019/03/16/LRUCache/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请博主吃包辣条
0%