LRU算法的原理与实现
一、LRU算法的原理
LRU是Least Recently Used的缩写，即最近最少使用算法，应用面非常的广泛，比如redis当中的内存淘汰策略。因为计算机的内存都是有限的，当用户访问的数据如果存在内存当中直接返回的给用户的话，效率会非常快，但是如果内存不存在，在去磁盘里面查找的，效率会大打折扣。所以我们希望在有限的内存空间当中，多存放点热点数据，用户不经常访问的数据，尽量淘汰掉，避免占用内存空间。
二、LRU算法实现-java
使用双向链表来实现LRU这篇文章已经用双向链表来实现过LRU算法了，但是基于双向链表的特性，使得该算法的时间复杂度为O(n)，显然不是最优的算法，那么有没有算法，可以达到O(1)，当然是有的，早早的计算机科学家已经想到，并且已经实现了。
在笔者介绍接下来的内容时，还是希望先了解一下两篇博文：
一、图解HashMap原理
二、图解LinkedHashMap
之前使用双向链表去实现LRU算法时，时间复杂度没有达到O(1)，主要原因在于遍历结点时，带来的时间开销，那么换句话说，要实现遍历结点时，时间复杂度为O(1)，第一时间想到的应该是hash数组，但是hash算法可能会存在不同的key值，产生相同的hash值，那么可以将不同key，但是相同hash值的结点，以单链表的形式存放。这样仅仅是实现了存取时间复杂度为O(1)，如何实现数据能够按访问顺序存放呢？并且增删的时间复杂度为O(1)，这个可以使用双向链表来实现，所以综合来讲，就是实现散列数组+双向链表来使用LRU，可以达到时间复杂度为O(1)。
逻辑视图如下:
LinkedHashMap逻辑视图.png
咋一看这个图乱的很，稍微解释一下，如果感觉理解上有点困难，可以先去了解一下之前推荐的两篇博文，那里会介绍的更加详细一点。
1.最左侧其实就是一个普通的数组，数组的大小必须是2的倍数，这个原因是什么呢？因为这个数组的存放方式是散列的，意思就是需要key.hashcode & (length -1)才能得出存放位置的方式，hash的好处是可以根据key值，在时间复杂度为O(1)的前提找到对应的存放位置，这也是我们的初衷，说到这里其实还没有解释为什么一定要是2的倍数，因为2的倍数-1，这个数的二进制，一定全是1，比如16-1=15，二进制表示就是1111，&运算符其实就是将值全部化成二进制逐位与，比如10111011 & 1111 = 1011 = 11，但是如果不是2的倍数，比如7-1=6，化成二进制就是0110，由于末位是0，不管什么二进制值与0110做&运算，一定是偶数，这样会导致散列分布不均匀。
2.不同key值，相同hash值，如何存放呢？相同的hash值做与运算一定能够得到相同的数组脚标，这些结点，以单链表的形式存在，就是图中数组右侧的单链表。
3.如何实现按访问顺序？上图除去数组和挂在数组右侧的单链表，还有绿色和黄色的单向箭头，在右上角还有一个双向链表的头指针。其实这些箭头就是维护不同结点的访问顺序，即双向链表。
总上所述，这种数据结构定义的结构体如下：
class Node{
Object key; //存放key值，用于计算存放数组脚标位置
Object value;//存放元素值
int hash;//存放key.hashcode
Node next;//维护单链表顺序
Node before;//维护双向链表顺序
Node after;
}
笔者用java实现如下，感兴趣可以用自己喜欢的语言去实现一遍，加深理解：
public class LeastRecentlyUsedWithLinkedHashMap {
/**
* 使用数组+双向链表可以使用LRU算法，并且可以达到O(1)复杂度
*/
private Object[] myLinkedHashMap = null; //hash数组
private int maxSize;
private int currSize;
entry head = null; // 双向链表的头结点
class entry {
Object key; //key值，可以用于计算存于哪个脚标
Object value; //对应数组里面存储的值
int hash; //hash(key)可以实现散列数组
entry next = null; //当不同的key，hash值相同时，会以单链表的形式下挂在该结点下面
entry before = null; //before和after实现双向链表，来维护数据的访问顺序
entry after = null;
}
public LeastRecentlyUsedWithLinkedHashMap(int maxSize) {
// 初始化一个头结点
this.maxSize = getMaxSize(maxSize); //hash数组大小必须为2的倍数
this.currSize = 0;
myLinkedHashMap = new Object[this.maxSize]; //申请的数组大小必须是2的倍数
head = new entry();
head.key = 0;
head.value = 0;
head.hash = head.key.hashCode();
head.next = head.before = head.after = null;
}
public int getMaxSize(int maxSize) {
// 获取大于当前大小，并且最接近2倍数的值
if (maxSize == 1){
return 2;
}
int capacity = 1;
while (capacity < maxSize)
capacity = capacity << 1;
return capacity;
}
/**
* 添加一个数据步骤：
* -》输入key和value值
* -》根据key计算出hash值，然后 K = hash & (maxSize-1)，计算出应该插入的脚标K值
* -》申请一个新的结点，将key和value进行赋值
* -》判断K脚标的结点上是否存在数据，如果存在数据，遍历该单链表，看是否存在相同的key值，如果
* 存在，替换掉原有结点，如果没有相同的key值，插入到链表的头部。
* -》使用双向链表维护插入的顺序
*/
public Boolean put(Integer key, Object value) {
int index = key.hashCode() & (this.maxSize - 1); //计算待插入的脚标
//新增一个结点
entry indexEntry = new entry();
indexEntry.key = key;
indexEntry.value = value;
indexEntry.hash = key.hashCode();
if (myLinkedHashMap[index] != null) {
//说明该结点已经有值,存在单链表
entry node = null;
if (myLinkedHashMap[index] instanceof entry) {
node = (entry) myLinkedHashMap[index];
} else {
return false;
}
for (; node != null; node = node.next) {
// 遍历结点所在的单链表
if (node.key.equals(key)) {
/**
* 表示找到了存在key值的结点，这个时候需要替换该结点的值，并且在
* 双向链表当中删除该结点，并且将该结点添加至双向链表的尾部。
*/
node.value = value;
removeDoubleLinkedListElem(node);
addElem(node);
return true;
} else {
continue;
}
}
if (node == null) {
/**
* 说明该结点所在的单链表当中不存在与key相等的结点，则需要将该结点插至
* 该单链表的第一个结点，并且更新双向链表。
*/
if (currSize == this.maxSize){
//双向链表已经处于full状态，则需要移除第一个结点
removeLinkedListElem(head.after);
removeDoubleLinkedListElem(head.after);
}
indexEntry.next = (entry)myLinkedHashMap[index]; //将新新增的结点插入到单链表的头部
myLinkedHashMap[index] = indexEntry; //将新增结点放置在hash数组上
addElem(indexEntry); //维护双向链表
return true;
}
} else {
//说明index位置上不存在值，那么直接插入即可，并且维护双向链表
if (currSize == this.maxSize){
//双向链表已经处于full状态，则需要移除第一个结点
removeLinkedListElem(head.after);
removeDoubleLinkedListElem(head.after);
}
myLinkedHashMap[index] = indexEntry;
addElem(indexEntry); //维护双向链表
return true;
}
return true;
}
public Object removeDoubleLinkedListElem(entry entry) {
//在双向链表当中删除该结点
Object returnObject = entry.value;
entry.before.after = entry.after;
entry.after.before = entry.before;
entry.before = entry.after = null;
this.currSize--;
return returnObject;
}
public Object removeLinkedListElem(entry entry){
int index = entry.hash & (this.maxSize - 1); //计算出该结点所在散列数组的脚标
entry currNode = null; //记录脚标所在结点的位置
entry delNode = null; //记录单链表待删除的结点
entry preNode = null; //记录单链表待删除结点的前一个结点位置
Object returnObject = null;
if (myLinkedHashMap[index] instanceof entry){
currNode = (entry)myLinkedHashMap[index];
}else{return -1;}
if (currNode.next == null && currNode.key.equals(entry.key)){
returnObject = currNode.value;
myLinkedHashMap[index] = null; //如果对应脚标的位置只有一个结点，直接置为空
return returnObject;
}else{
for (preNode = currNode,delNode = currNode.next;delNode != null;preNode = delNode,delNode = delNode.next){
if (delNode.key.equals(entry.key)){
//说明已经找到对应的结点
returnObject = delNode.value;
if (delNode.next != null){
//表示该结点不处于单链表的尾部
preNode.next = delNode.next;
delNode.next = null;
return returnObject;
}else{
preNode.next = null;
return returnObject;
}
}else{continue;}
}
return -1;
}
}
public Boolean addElem(entry entry) {
//在双向链表的尾部添加元素结点
if (currSize == 0){
// 表示是空的双向链表
entry.before = entry.after = head;
head.before = head.after = entry;
this.currSize++;
return true;
}
entry.after = head;
entry.before = head.before;
head.before.after = entry;
head.before = entry;
this.currSize++;
return true;
}
/**
* 查找一个数据步骤
* -》根据key值计算hashcode，然后 K = hash & (maxSize-1)，计算出脚标
* -》如果该结点是一个单链表，就从头结点开始遍历，查找与key相同的结点，如果没找到返回-1
* 如果找到了，在双向链表当中删除该结点，然后将该结点插到双向链表的尾部
*/
public Object get(Object key) {
int index = key.hashCode() & (this.maxSize - 1);
entry node = null;
if (myLinkedHashMap[index] instanceof entry) {
node = (entry) myLinkedHashMap[index];
} else {
return -1; //表示未查找到数据
}
if (node.next != null){
//表示该结点存在单链表，需要进行遍历
for (;node != null;node = node.next){
if (node.key.equals(key)){
removeDoubleLinkedListElem(node);
addElem(node);
return node.value;
}else{
continue;
}
}
if (node == null){
//说明未存在key
return -1;
}
}else{
if (node.key.equals(key)){
removeDoubleLinkedListElem(node);
addElem(node);
return node.value;
} else{return -1;}
}
return -1;
}
//实现toString功能，方便测试
public String toString(){
StringBuffer sb = new StringBuffer();
if (currSize == 0){
return "";
}
entry currNode = head.after;
for (;currNode != head;currNode = currNode.after){
if (currNode.after != head){
sb.append(currNode.value);
sb.append(",");
}else {
sb.append(currNode.value);
}
}
return sb.toString();
}
public static void main(String[] args) {
}
}
其实以上实现底层原理就是LinkedHashMap的实现原理，只不过笔者做了一些简化，去掉了繁琐的继承，扩容等，突出了算法核心，如果读者感兴趣也可以去研究一下LinkedHashMap的源码。
使用LinkedHashMap来实现LRU算法：
import java.util.LinkedHashMap;
public class LRULinkedHashMap {
public static void main(String[] args) {
LinkedHashMap<Object, Object> objectObjectLinkedHashMap = new LinkedHashMap<Object, Object>(1,0.75f,true);
objectObjectLinkedHashMap.put(1,"zhangsan");
objectObjectLinkedHashMap.put(2,"lisi");
objectObjectLinkedHashMap.put(3,"wangwu");
objectObjectLinkedHashMap.get(1);
System.out.println(objectObjectLinkedHashMap.toString());
}
}
看起来是不是简单了很多，因为LinkedHashMap底层已经封装好了，我们直接调用就好，但是作为一个想要变优秀的码农，一定要知其然知其所以然。
三、时间复杂度分析
使用散列+双向链表的方式是如何实现O(1)复杂度的？在实现LRU算法过程中，无非两种操作，查找和修改，使用散列数组实现查找时间复杂度为O(1)，使用双向链表实现修改复杂度为O(1)，并且双向链表还可以维护访问顺序，所以使用这种方式，可以达到O(1)。
