LRU算法实现

LRU缓存

由于内存是有限的，因此缓存总有满的时候，那么当缓存满了的时候，这时候又有新的数据需要加入到缓存中时，我们该怎么办了？没什么别的办法，只有从缓存中删除旧数据为新数据腾出空间，那么究竟删除原来缓存的哪些数据了？这就涉及到缓存的替换策略，LRU就是一种缓存策略。

LRU，Least Recently Used的简写，翻译过来就是“最近最少使用”， 其淘汰旧数据的策略是，距离当前最久没有被访问过的数据应该被淘汰。

LRU原理

假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。

这样设计可能问题很多，内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。

那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的，我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用双向链表。

HashMap+双向链表

基于 HashMap 和 双向链表实现 LRU的整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示：

LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

代码实现

// 双项链表

function DLinkedNode(key, data) {
	this.key = key;
	this.data = data;
	this.next = null; // 指向下一个节点
	this.prev = null; // 指向前一个节点
}

function LRUCache(capacity) {
	var cache = {};
	var count = 0;
	var capacity;
	
	head = new DLinkedNode();
	tail = new DLinkedNode();
	tail.prev = head;
	head.next = tail;


	this.get = function(key) {
		var node = cache[key];
		if (!node) return null;
		this.moveToHead(node);
		return node.data;
	}

	this.set = function(key, data) {
		var node = cache[key];
		if (!node) {
			node = new DLinkedNode(key, data);
			cache[key] = node;
			this.addNode(node);
			count++;
			if (count > capacity) {
				var tail = this.popTail();
				delete cache[tail.key];
				count--;
			}
		} else {
			node.data = data;
			this.moveToHead(node);
		}
	}

	this.addNode = function(node) {
		node.prev = head;
		node.next = head.next;
		head.next.prev = node;
		head.next = node;
	}

	this.removeNode = function(node) {
		var prev = node.prev;
		var next = node.next;
		prev.next = next;
		next.prev = prev;
	}

	this.moveToHead = function(node) {
		this.removeNode(node);
		this.addNode(node);
	}

	this.popTail = function() {
		var preNode = tail.prev;
		this.removeNode(preNode);
		return preNode;
	}
}

参考文档

• 图解LinkedHashMap原理