Java实现简单LRU缓存机制的方法

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

二、LRU的使用

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
   cache.put(1, 1);
   cache.put(2, 2);
   cache.get(1);    // 返回 1
   cache.put(3, 3);  // 该操作会使得密钥 2 作废

第一步：创建一个长度为2的LRUCache

第二步：cache.put(1, 1);放入key=1，value=1的数据

第三步：cache.put(2，2);放入key = 2，value = 2的数据
(因为2刚使用，所有把2移动到前面）

第四步：cache.get(1);获取key = 1的数据
（因为我们刚使用了1，所以把1移动到前面）

第五步：cache.put(3，3);放入key = 3，value = 3的数据
（因为3刚放进，所以放前面，又因为容量只有2，需要移除原先的1个。只因key = 2是最近最少使用的（key = 1刚get()过)，所以移除2。

三、LRU的实现机制

算法：

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

1）双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

2）哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

一、初始化：

二、cache.put(1，1)：

三、cache.put(2，2)：

四、cache.get(1)：

五、cache.put(3,3)：

四、代码如下

import java.io.*;
import java.util.HashMap;

public class test {

public static void main(String args[]) throws IOException {

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

/**
* 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put
*/
class LRUCache {

private HashMap<Integer,LinkedNode> cache = new HashMap();//方便通过key快速定位结点
 private int size;
 private int capacity;
 private LinkedNode head,tail;
 class LinkedNode{
   int key;
   int value;
   LinkedNode pre;
   LinkedNode next;
 }
 public LRUCache(int capacity) {
   this.size = 0;
   this.capacity = capacity;
   head = new LinkedNode();
   tail = new LinkedNode();
   head.next = tail;
   tail.pre = head;
 }

/**
  * 移除节点
  * @param node
  */
 private void removeNode(LinkedNode node) {
   LinkedNode preNode = node.pre;
   LinkedNode nextNode = node.next;
   preNode.next = nextNode;
   nextNode.pre = preNode;
 }

/**
  * 添加节点到头部
  * @param node
  */
 private void addNode(LinkedNode node) {
   node.pre = head;
   node.next = head.next;
   head.next.pre = node;
   head.next = node;
 }

/**
  * 将节点移动到头部
  * @param node
  */
 private void moveToHead(LinkedNode node) {
   removeNode(node);
   addNode(node);
 }

/**
  * 获取数据
  * @param key
  * @return
  */
 public int get(int key) {
   LinkedNode node = cache.get(key);
   if(node != null) {
     moveToHead(node);
   }else{
     return -1;
   }
   return node.value;
 }

/**
  * 写入数据
  * @param key
  * @param value
  */
 public void put(int key, int value) {
   LinkedNode node = cache.get(key);
   //存在
   if(node != null) {
     node.value = value;//可能更新数据
     moveToHead(node);
   }
   //不存在
   else{
     LinkedNode newNode = new LinkedNode();
     newNode.key = key;
     newNode.value = value;
     cache.put(key,newNode);//更新Map
     addNode(newNode);//添加结点到头部
     size++;//更新结点数
     if(size > capacity) {//如果结点数超过容量大小
       LinkedNode tailPre = tail.pre;
       cache.remove(tailPre.key);//更新Map
       removeNode(tailPre);//删除最后一个结点（尾结点的前一个结点）
       size--;
     }
   }
 }
}

总结：自己实现的简单LRU总归太简单了，要是想完善或者实现更真实的LRU，不妨参考一下Redis中的LRU。(◔◡◔)

来源：https://blog.csdn.net/Milan_1in/article/details/106327306