LRU算法介紹
LRU是Least Recently Used的縮寫，即最近最少使用，常用于頁面置換算法，為虛擬頁式存儲管理服務(wù)。LRU算法的提出，是基于這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用。反過來說，已經(jīng)很久沒有使用的頁面很可能在未來較長的一段時間內(nèi)不會被用到。這個，就是著名的局部性原理。此外，LRU算法也經(jīng)常被用作緩存淘汰策略。本文將基于LRU算法的思想，使用Java語言實現(xiàn)一個我們自己的緩存工具類。

實現(xiàn)方式
最常見的實現(xiàn)是使用一個雙向鏈表保存緩存數(shù)據(jù)，詳細(xì)算法實現(xiàn)如下：

1. 新數(shù)據(jù)插入到鏈表頭部；
2. 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部；
3. 當(dāng)鏈表滿的時候，將鏈表尾部的數(shù)據(jù)丟棄。

優(yōu)點：實現(xiàn)簡單。
缺點：每次訪問都需要更新鏈表，因此代價略高。

代碼實現(xiàn)
本文將提供兩個不同的實現(xiàn)版本，不過實現(xiàn)思想都是一模一樣的。

版本一：

/**
?* 在版本一中，我們自己利用HashMap和一個簡單的雙向鏈表來實現(xiàn)LRU緩存
?*/
class LRUCache {

? ? // 雙向鏈表節(jié)點定義
? ? class Node {
? ? ? ? int key;
? ? ? ? int val;
? ? ? ? Node prev;
? ? ? ? Node next;
? ? }
? ??
? ? private int capacity;
? ? //保存鏈表的頭節(jié)點和尾節(jié)點
? ? private Node first;
? ? private Node last;
? ??
? ? private Map<Integer, Node> map;

? ? public LRUCache(int capacity) {
? ? ? ? this.capacity = capacity;
? ? ? ? map = new HashMap<>(capacity);
? ? }
? ??
? ? public int get(int key) {
? ? ? ? Node node = map.get(key);
? ? ? ? //為空返回-1
? ? ? ? if (node == null) {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? moveToHead(node);
? ? ? ? return node.val;
? ? }
? ??
? ? private void moveToHead(Node node) {
? ? ? ? if (node == first) {
? ? ? ? ? ? return;
? ? ? ? } else if (node == last) {
? ? ? ? ? ? last.prev.next = null;
? ? ? ? ? ? last = last.prev;
? ? ? ? } else {
? ? ? ? ? ? node.prev.next = node.next;
? ? ? ? ? ? node.next.prev = node.prev;
? ? ? ? }
? ? ? ??
? ? ? ? node.prev = first.prev;
? ? ? ? node.next = first;
? ? ? ? first.prev = node;
? ? ? ? first = node;
? ? }
? ??
? ? public void put(int key, int value) {
? ? ? ? Node node = map.get(key);
? ? ? ??
? ? ? ? if (node == null) {
? ? ? ? ? ? node = new Node();
? ? ? ? ? ? node.key = key;
? ? ? ? ? ? node.val = value;
? ? ? ? ? ??
? ? ? ? ? ? if(map.size() == capacity) {
? ? ? ? ? ? ? ? removeLast();
? ? ? ? ? ? }
? ? ? ? ? ??
? ? ? ? ? ? addToHead(node);
? ? ? ? ? ? map.put(key, node);
? ? ? ? } else {
? ? ? ? ? ? node.val = value;
? ? ? ? ? ? moveToHead(node);
? ? ? ? }
? ? }
? ??
? ? private void addToHead(Node node) {
? ? ? ? if (map.isEmpty()) {
? ? ? ? ? ? first = node;
? ? ? ? ? ? last = node;
? ? ? ? } else {
? ? ? ? ? ? node.next = first;
? ? ? ? ? ? first.prev = node;
? ? ? ? ? ? first = node;
? ? ? ? }
? ? }
? ??
? ? private void removeLast() {
? ? ? ? map.remove(last.key);
? ? ? ? Node prevNode = last.prev;
? ? ? ? if (prevNode != null) {
? ? ? ? ? ? prevNode.next = null;
? ? ? ? ? ? last = prevNode;
? ? ? ? }
? ? }
? ??
? ? @Override
? ? public String toString() {
? ? ?? ?return map.keySet().toString();
? ? }
? ??
? ? public static void main(String[] args) {
? ? ?? ?LRUCache cache = new LRUCache(3);
? ? ? ? cache.put(1, 1);
? ? ? ? cache.put(2, 2);
? ? ? ? cache.put(3, 3);
? ? ? ? cache.get(1);
? ? ? ? cache.put(4, 3);
? ? ? ? System.out.println(cache);
?? ?}
}
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
打印結(jié)果：
[4, 1, 3]
1
2
可以看到這種實現(xiàn)方式 get 和 put 的操作時間復(fù)雜度都是O(1)的。

版本二：

其實JDK已經(jīng)為我們提供了一個基于HashMap和雙向鏈表實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，它就是LinkedHashMap，它內(nèi)部維護(hù)的雙向鏈表，可以幫助我們維護(hù)兩種順序：

插入順序
LRU順序
下面簡單的介紹下LinkedHashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
1
它繼承自HashMap，同樣具有快速查找特性。

? ? /**
? ? ?* The head (eldest) of the doubly linked list.
? ? ?*/
? ? transient LinkedHashMap.Entry<K,V> head;

? ? /**
? ? ?* The tail (youngest) of the doubly linked list.
? ? ?*/
? ? transient LinkedHashMap.Entry<K,V> tail;
1
2
3
4
5
6
7
8
9
內(nèi)部維護(hù)了一個雙向鏈表，用來維護(hù)插入順序或者 LRU 順序。
另外根據(jù)注釋，我們可以看出來，頭節(jié)點head是最老的節(jié)點，而尾節(jié)點是最近一次被訪問的節(jié)點，所以維護(hù)LRU順序時，容量用完后，再執(zhí)行新數(shù)據(jù)的插入的話，會移除頭節(jié)點。

final boolean accessOrder;
1
accessOrder決定了維護(hù)的是哪一種順序，默認(rèn)為 false，此時維護(hù)的是插入順序。為true時，維護(hù)的就是LRU順序了。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
1
2
LinkedHashMap 最重要的是上述這兩個用于維護(hù)順序的函數(shù)，它們會在 put、get 等方法中調(diào)用。

void afterNodeAccess(Node<K,V> e) { // move node to last
? ? LinkedHashMap.Entry<K,V> last;
? ? if (accessOrder && (last = tail) != e) {
? ? ? ? LinkedHashMap.Entry<K,V> p =
? ? ? ? ? ? (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
? ? ? ? p.after = null;
? ? ? ? if (b == null)
? ? ? ? ? ? head = a;
? ? ? ? else
? ? ? ? ? ? b.after = a;
? ? ? ? if (a != null)
? ? ? ? ? ? a.before = b;
? ? ? ? else
? ? ? ? ? ? last = b;
? ? ? ? if (last == null)
? ? ? ? ? ? head = p;
? ? ? ? else {
? ? ? ? ? ? p.before = last;
? ? ? ? ? ? last.after = p;
? ? ? ? }
? ? ? ? tail = p;
? ? ? ? ++modCount;
? ? }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
當(dāng)一個節(jié)點被訪問時，如果 accessOrder 為 true，則會將該節(jié)點移到鏈表尾部。也就是說指定為 LRU 順序之后，在每次訪問一個節(jié)點時，會將這個節(jié)點移到鏈表尾部，保證鏈表尾部是最近訪問的節(jié)點，那么鏈表首部就是最近最少使用的節(jié)點。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
? ? LinkedHashMap.Entry<K,V> first;
? ? if (evict && (first = head) != null && removeEldestEntry(first)) {
? ? ? ? K key = first.key;
? ? ? ? removeNode(hash(key), key, null, false, true);
? ? }
}
1
2
3
4
5
6
7
在 put 等操作之后執(zhí)行，當(dāng) removeEldestEntry() 方法返回 true 時會移除最老的節(jié)點，也就是鏈表首部節(jié)點 first。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
? ? return false;
}
1
2
3
removeEldestEntry() 默認(rèn)返回 false，如果需要讓它為 true，需要繼承 LinkedHashMap 并且重寫這個方法，這是實現(xiàn) LRU 緩存的關(guān)鍵，通過移除最近最少使用的節(jié)點，從而保證緩存空間足夠，并且緩存的數(shù)據(jù)都是熱點數(shù)據(jù)。

接下來我們基于JDK提供給我們的LinkedHashMap來實現(xiàn)LRU緩存

public class LRUCache<K,V> extends LinkedHashMap<K, V>{
?? ?
?? ?//首先設(shè)定最大緩存空間 MAX_ENTRIES 為 3；
?? ?private static final int MAX_ENTRIES = 3;
?? ?
?? ?//之后使用LinkedHashMap的構(gòu)造函數(shù)將 accessOrder設(shè)置為 true，開啟 LRU順序；
?? ?public LRUCache() {
?? ??? ?super(MAX_ENTRIES, 0.75f, true);
?? ?}
?? ?
?? ?//最后覆蓋removeEldestEntry(）方法實現(xiàn)，在節(jié)點多于 MAX_ENTRIES 就會將最近最少使用的數(shù)據(jù)移除。
?? ?//因為這個函數(shù)默認(rèn)返回false，不重寫的話緩存爆了的時候無法刪除最近最久未使用的節(jié)點
?? ?@Override
?? ?protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
?? ??? ?//在容量超過最大允許節(jié)點數(shù)的時候返回true，使得在afterNodeInsertion函數(shù)中能執(zhí)行removeNode()
?? ??? ?return size() > MAX_ENTRIES;
?? ?}
?? ?
?? ?public static void main(String[] args) {
?? ? ? ?LRUCache<Integer, Integer> cache = new LRUCache<>();
?? ? ? ?cache.put(1, 1);
?? ? ? ?cache.put(2, 2);
?? ? ? ?cache.put(3, 3);
?? ? ? ?cache.get(1);
?? ? ? ?cache.put(4, 4);
?? ? ? ?System.out.println(cache.keySet());
?? ?}
}
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
打印結(jié)果

[3, 1, 4]
1
版本二參考內(nèi)容：CyC2018 CS-Notes
————————————————
版權(quán)聲明：本文為CSDN博主「許大俠0610」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/u013568373/article/details/90607083

總結(jié)

以上是生活随笔為你收集整理的LRU算法及Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。