缓存淘汰算法之 LRU算法 leetcode 146. LRU Cache

缘起

因为作为一个java工程师，缓存组件是必须要深入理解的. 提到缓存的话，有两点必须要考虑

  1. 缓存和持久化数据的一致性问题
  2. 缓存数据的过期问题，这就涉及淘汰算法. 因为缓存大小是有限的.

常见的淘汰算法有 FIFO、LRU、LFU（具体含义见【1】）， 一个优秀的缓存框架（例如ehcache）必须要实现这三种淘汰算法.

这里的题目涉及LRU算法的数据结构的设计.

ps: 这里多说一句，在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来高效地更新和访问其中的元素。

传送门

分析

题意如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

此题其实比较严格——必须set、get两种操作都要到达O(1)才行，不然就会被卡. 那么思路是什么呢? 其实计算机领域所谓的空间换时间、时间换空间，就是人生中的”有得必有失”. 如果你想两种操作都快的话，就必须要在进行操作的时候额外进行维护点儿什么. 记录点儿什么，不然怎么能到达常数时间进行操作呢?

算法是简单的，使用一个HashMap判重——有没有插入过. 如果有的话，更改之. 如果没有的话，则插入之. 取的话，也很简单，就是直接get. 读过HashMap的源码的童鞋都知道HashMap本质就是一个哈希表. 因为本题插入的都是数字，所以这里唯一可能冲突就是HashMap的table属性长度不够, 导致哈希冲突（即不是哈希值相等，而是模掉长度之后相等）. 否则的话，是不会哈希冲突的, 所以HashMap伊始的容量取得大一点比较好.

然后维护一根链表为淘汰机制做准备. 只要set/get了的话，则就表示它最近被用过了. 就把它插到链表的头部. 一旦容量超过了缓存容量的上限，则删除链表的末位元素以及HashMap中相应的元素（因为HashMap是哈希表，所以相应的移除并不是遍历，消耗的时间也是O(1)的）.

Java实现如下（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
import java.util.HashMap;

class LRUCache {

	public LRUCache(int capacity) {
		this.map = new HashMap<>(capacity);
		this.capacity = capacity;
		this.head = new CacheNode(-1, -1);
		this.tail = new CacheNode(-1, -1);
		head.next = tail;
		tail.prev = head; // 初始化
	}

	public int get(int key) {
		CacheNode cacheNode = map.get(key);
		if (cacheNode == null) {
			return -1;
		}
		move2front(cacheNode); // 将cache节点移动到首节点（首节点是头结点的后继）
		return cacheNode.value;
	}

	public void put(int key, int value) {
		CacheNode cacheNode = map.get(key);
		if (cacheNode != null) { // 如果存在此key的话，就覆盖
			cacheNode.value = value;
		} else {
			cacheNode = new CacheNode(key, value);
			map.put(key, cacheNode); // 插入新的节点
		}
		move2front(cacheNode); // 将此缓存节点移动到首节点
		if (this.map.size() > this.capacity) { // 如果超过了缓存的容量
			map.remove(tail.prev.key); // 移除map中相应的节点
			removeLast(); // 移除链表的末尾节点
		}
	}

	private HashMap<Integer, CacheNode> map;

	private CacheNode head;
	private CacheNode tail; // 双向（非循环）链表的头尾(一般加一个头尾会省事儿不少)
	private int capacity; // 缓存的容量

	private static class CacheNode {
		private CacheNode next;
		private CacheNode prev; // 双向链表
		private Integer key;
		private Integer value;

		public CacheNode(Integer key, Integer value) {
			this.key = key;
			this.value = value;
			this.next = this.prev = null;
		}

	}

	private void move2front(CacheNode cacheNode) { // 将cacheNode移动到首节点去
		if (!(cacheNode.next == null && cacheNode.prev == null)) { // 如果不是新建节点的话, 需要先移除
			cacheNode.prev.next = cacheNode.next;
			cacheNode.next.prev = cacheNode.prev;
		}
		cacheNode.next = head.next;
		head.next.prev = cacheNode;
		head.next = cacheNode;
		cacheNode.prev = head; // 直接移动到首节点(头插)
	}

	private void removeLast() { // 移除链表末尾节点
		tail.prev.prev.next = tail;
		tail.prev = tail.prev.prev;
	}

	/*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
	}*/
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

ac结果如下

1
2
3
4
5
6
7
8
9
执行结果：

通过

显示详情

执行用时 :111 ms, 在所有 Java 提交中击败了92.94%的用户

内存消耗 :50.4 MB, 在所有 Java 提交中击败了99.67%的用户

额，由此可见，我比大部分java工程师的在此题上的表现是胜出的~ 嘿嘿~

参考

【1】https://www.cnblogs.com/jtlgb/p/6394403.html

【2】https://yfsyfs.github.io/2019/06/07/java-util-HashMap-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/