LRU缓存淘汰算法
来源公众号：算法面试题
简介
LRU，最近最少使用算法，即当要对数据进行淘汰时，先将最近最久未使用的数据淘汰（亦说最近最久未使用算法），是一种缓存淘汰算法。
意义：大家知道计算机的内存是有限的，当我们对一些数据一直缓存而不淘汰的话，那么内存总会被占满的，特别是服务器，造成的后果是可怕的。
应用场景：内存的页面淘汰、站内搜索关键字的缓存淘汰（详见：《如何应对算法面试题》 来源公众号：算法面试题）等。
题目
（猫眼面试题，来源于剑指offer）
运用你所掌握的数据结构，设计和实现一个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思考三分钟再往下看效果更佳哦
思路
本题属于一道比较难的题，难点在于O（1）的时间复杂度，首先我们会想到用链表来缓存，为了方便淘汰最后一条数据时将尾指针前移一位，我们需要使用双链表,于是我们定义结点如下。
接下来进行get（key）操作时对整个链表进行遍历（时间复杂度O（n），n为缓存容量），直到找到key结点返回对应的值（找不到返回-1），注：若结点存在，访问完结点后还应将结点移到链表首部。
接下来是put（key，val）操作，首先需要对链表遍历（时间复杂度O（n），n为缓存容量）以确定key结点是否已经存在，若存在将结点移到链表首部并更新结点值为val；若不存在，则需要新建一个结点（key，val），并插入首部，需注意的是若超过容量上限，则删除最后一个结点。
不难发现，上面的实现方法get与put时间复杂度均为O（n），时间主要浪费在了遍历链表（查找key结点）上，那么我们如何来优化查找key结点的效率呢？
谈到查找并且是O（1）复杂度，那么我们不难想到哈希表。结合本题我们可以创建一个这样的Map，Map结点的键为双链表结点的key，Map结点的值为指向双链表结点的指针，这样我们通过链表结点的key就可以在O（1）时间内找到对应结点了。需要注意的是在对双链表增加或淘汰结点时，也要对Map同步添加或删除结点。
代码实现
下面是作者用JavaScript实现的代码，仅供参考！（建议大家自己动手实现一遍）
function Node(key, val) {
//定义双链表的结点
this.key = key;
this.val = val;
this.pre = this.next = null;
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity;
//定义头结点，不存值，作用方便结点的插入和删除
//双链表，head始终指向头结点，tail始终指向最后一个结点
this.tail = this.head = new Node(-2, -2);
//map，键是结点的属性key，值是指向结点的指针
//map作用保证了O（1）时间内实现get与put操作
this.map = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let node = this.map.get(key);
//当key值不存在或已被淘汰时，返回-1
if(node === undefined) return -1;
//当key值存在于链表中，返回值并将对应结点移到链表首部
//注：链表具有头结点，故移到首部，实际上是移到头结点之后
node.pre.next = node.next;
if(this.tail != node) {
node.next.pre = node.pre;
} else {
this.tail = this.tail.pre;
}
node.pre = this.head;
node.next = this.head.next;
if(node.next != null) node.next.pre = node;
else this.tail = node;
this.head.next = node;
return node.val;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let node = this.map.get(key);
if(node !== undefined) {
//如果key存在于双链表中，更新值并将key对应的那个结点移到链表首部
//注：链表具有头结点，故移到首部，实际上是移到头结点之后
node.val = value;
node.pre.next = node.next;
if(this.tail != node) {
node.next.pre = node.pre;
} else {
this.tail = this.tail.pre;
}
node.pre = this.head;
node.next = this.head.next;
if(node.next != null) node.next.pre = node;
else this.tail = node;
this.head.next = node;
} else {
//如果key不在双链表中，创建一个新结点，并将结点插入链表首部
//注：链表具有头结点，故插入首部，实际上是插入到头结点之后
node = new Node(key, value);
if(this.map.size == 0) {
this.tail = node;
node.pre = this.head;
node.next = this.head.next;
this.head.next = node;
} else {
node.pre = this.head;
node.next = this.head.next;
node.next.pre = node;
this.head.next = node;
}
if(this.map.size >= this.capacity) {
//如果缓存容量达到上限，需要将最近最久未使用的那条数据淘汰
//即淘汰最后一条数据
this.map.delete(this.tail.key);
this.tail = this.tail.pre;
this.tail.next = null;
}
//将新结点的key注册到map中，方便在O（1）的时间内获取到值
this.map.set(key, node);
}
};
完毕，小伙伴们可以愉快地去敲键盘实现自己的代码了！