Java 手写LRU缓存淘汰算法

目录

• 概述

• LRU 的原理

• LRU 算法的实现

• LRU 算法描述

• LRU 算法代码实现

• 方法一

• 方法二

• 方法三

• 总结

概述

LRU 算法全称为 Least Recently Used 是一种常见的页面缓存淘汰算法，当缓存空间达到达到预设空间的情况下会删除那些最久没有被使用的数据 。

常见的页面缓存淘汰算法主要有一下几种：

• LRU 最近最久未使用

• FIFO 先进先出置换算法 类似队列

• OPT 最佳置换算法 （理想中存在的）

• NRU Clock 置换算法

• LFU 最少使用置换算法

• PBA 页面缓冲算法
  

LRU 的原理

LRU 算法的设计原理其实就是计算机的 局部性原理（这个 局部性原理 包含了 空间局部性 和 时间局部性 两种策略）。LRU 算法主要是依据 时间局部性策略 来设计的。

这个策略简单来说就是，如果一个数据被访问了，那么在短时间内它还会被访问。

同样的，针对一个缓存数据，如果其使用的时间越近，那么它被再次使用的概率就越大，反之一个缓存数据如果很长时间未被使用，那它会被再次使用的概率就会很小。因而当缓存空间不足时，我们优先删除最久未被使用的缓存数据，进而提高缓存命中率。

LRU 算法的实现

LRU 算法描述

缓存在使用时，核心 API 有两个：

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

具体使用的例子如下：

//初始化一个缓存，并将缓存空间设置为2
LRUCache cache = new LRUCache(2);

cache.put(1,1); // cache = [(1,1)]
cache.put(2,2); // cache = [(2,2),(1,1)]
cache.get(1); //返回1
cache.put(3,3) //cache = [(3,3),(2,2)]，缓存空间已满，需要删除空间腾出位置，因而删除最久未被使用的(1,1)
cache.get(1); //返回 -1 因为(1,1)已经被删除，因而返回 -1

LRU 算法代码实现

分析上面的算法操作，如果想要让 put 和 get 方法的时间复杂度位 O(1)，cache 的数据结构应该具有如下特点：

1. cache 中的元素必须是具有时序的，这样才能区分最近使用的和最久未使用的数据

2. 在 cache 中能够快速的通过 key 来找到对应的 val。

3. 每次访问 cache 的某个 key 时需要将这个元素变成最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。
   

那么有什么数据结构同时符合上边所有的要求那？HashMap 可以根据某个 key 快速定位到对应的 val，但是它不具有时序性（存储的数据没有顺序）。LinkedList 似乎支持快速插入和删除元素，而且具有固定顺序，但它并不支持快速查找。所以我们可以考虑将两者结合起来形成一种新的数据结构 LinkedHashMap。

LRU 算法的核心数据结构就是哈希链表，它是双向链表和哈希表的结合体。其具体数据结构如下图所示：

借助这个数据结构我们来注意分析上边的条件：

1. 如果每次默认从链表尾部添加元素，那么显然越靠近尾部的元素越是最近使用的，越是靠近头部的元素越是最久未被使用的。

2. 对于某一个 key，可以通过哈希表快速定位到对应的 val 上

3. 链表显然支持快速插入和快速删除。
   

方法一

在 Java 中本身是有 LinkedHashMap 这个数据结构的，但是为了了解算法的细节，我们尝试自己实现一遍 LRU 算法。

首先我们需要定义一个双向链表，为了简化，key 和 val 都设置称 int 类型。

class Node {
   public int key,val;
   public Node next, pre;
   public Node(int key, int val) {
       this.key = key;
       this.val = val;
   }
}

//构建一个双向链表，实现一个LRU算法必须的API
class DoubleList{
   //头尾虚节点
   private Node head, tail;
   //用来记录链表元素数量
   private int size;
   //初始化链表
   public DoubleList() {
   head = new Node(0, 0);
   tail = new Node(0, 0);
   head.next = tail;
   tail.pre = head;
   size = 0;
}
   //从尾部添加一个元素
   public Node addLast(Node x) {
   x.pre = tail.pre;
   x.next = tail;
   tail.pre.next = x;
   tail.pre = x;
   size++;
   return x;
   }
   //删除某一个元素(x必定存在于双向链表中)
   public Node remove(Node x) {
   x.pre.next = x.next;
   x.next.pre = x.pre;
   size--;
   return x;
   }
   //删除第一个元素
   public Node removeFirst() {
   //判断当前size是否为空
   if(head.next == tail) {
   return null;
   }
   return remove(head.next);
   }

//返回链表长度
   public int size() {
   return this.size;
   }
}

有了双向链表，只需要在 LRU 算法的基础上把它和 HashMap 结合起来就可以打出整个算法的一个基本框架。

class LRUCache {
private HashMap<Integer,Node> map;
private DoubleList cache;
private int capacity;
   public LRUCache(int capacity) {
   this.capacity = capacity;
   map = new HashMap<>();
   cache = new DoubleList();
   }
   public int get(int key) {
//具体实现
   }

public void put(int key, int value) {
//具体实现
   }
}

由于要同时维护一个双向链表 cache 和一个哈希表 map，在编写的过程中容易漏掉一些操作，因而我们可以**在这两种数据结构的基础上，抽象出一层 API。**尽量避免 get 和 put 操作直接操作 map 和 cache 的细节。

//封装HashMap和链表组合在一起常用的一些操作
//将某一个key提升为最近使用
private void makeRecently(int key) {
   // ????? 不需要对map中key和Node的映射关系进行维护吗？
   //cache 本身地址并没有变化所以不需要重新来维护key和Node的关系
   Node x = map.get(key);
   cache.remove(x);
   cache.addLast(x);
}
//添加最近使用的元素
private void addRecently(int key, int val) {
   Node x = new Node(key,val);
   cache.addLast(x);
   map.put(key, x);
}
//删除某一个key
private void deleteKey(int key) {
   Node x = map.get(key);
   //从链表中删除节点
   cache.remove(x);
   //删除key->x的映射关系
   map.remove(key);
}
//删除最久未使用元素
private void removeLeastRecently() {
   //删除链表中的第一个节点
   Node deleteNode = cache.removeFirst();
   //删除map中的映射关系
   map.remove(deleteNode.key);
}

进而我们便可以写出完整的代码：

import java.util.HashMap;

/**
方法一：不使用LinkedHashMap，完全从双向链表开始写
**/
class LRUCache {
private HashMap<Integer,Node> map;
private DoubleList cache;
private int capacity;
   public LRUCache(int capacity) {
   this.capacity = capacity;
   map = new HashMap<>();
   cache = new DoubleList();
   }

public int get(int key) {
   if(!map.containsKey(key)) {
   return -1;
   }
   makeRecently(key);
   return map.get(key).val;
   }

public void put(int key, int value) {
   //该节点已经存在
   if(map.containsKey(key)) {
   deleteKey(key);
   addRecently(key, value);
   return;
   }
   if(capacity == cache.size()) {
   removeLeastRecently();
   }
   //添加为最近使用的元素
   addRecently(key, value);
   }
 //封装HashMap和链表组合在一起常用的一些操作
 //将某一个key提升为最近使用
 private void makeRecently(int key) {
// ????? 不需要对map中key和Node的映射关系进行维护吗？
//cache 本身地址并没有变化所以不需要重新来维护key和Node的关系
 Node x = map.get(key);
 cache.remove(x);
 cache.addLast(x);
 }
 //添加最近使用的元素
 private void addRecently(int key, int val) {
 Node x = new Node(key,val);
 cache.addLast(x);
 map.put(key, x);
 }
 //删除某一个key
 private void deleteKey(int key) {
 Node x = map.get(key);
 //从链表中删除节点
 cache.remove(x);
 //删除key->x的映射关系
 map.remove(key);
 }
 //删除最久未使用元素
 private void removeLeastRecently() {
 //删除链表中的第一个节点
 Node deleteNode = cache.removeFirst();
 //删除map中的映射关系
 map.remove(deleteNode.key);
 }
}

class Node {
   public int key,val;
   public Node next, pre;
   public Node(int key, int val) {
       this.key = key;
       this.val = val;
   }
}
//构建一个双向链表，实现一个LRU算法必须的API
class DoubleList{
   //头尾虚节点
   private Node head, tail;
   //用来记录链表元素数量
   private int size;
   //初始化链表
   public DoubleList() {
   head = new Node(0, 0);
   tail = new Node(0, 0);
   head.next = tail;
   tail.pre = head;
   size = 0;
}
   //从尾部添加一个元素
   public Node addLast(Node x) {
   x.pre = tail.pre;
   x.next = tail;
   tail.pre.next = x;
   tail.pre = x;
   size++;
   return x;
   }
   //删除某一个元素(x必定存在于双向链表中)
   public Node remove(Node x) {
   x.pre.next = x.next;
   x.next.pre = x.pre;
   size--;
   return x;
   }
   //删除第一个元素
   public Node removeFirst() {
   //判断当前size是否为空
   if(head.next == tail) {
   return null;
   }
   return remove(head.next);
   }

//返回链表长度
   public int size() {
   return this.size;
   }
}

至此，我们已经完全掌握了 LRU 算法的原理和实现了，最后我们可以通过 Java 内置的类型 LinkedHashMap 来实现以下 LRU 算法。

方法二

在正式编写之前，我们简单说是说这个 LinkedHashMap。

LinkedHashMap 是 HashMap 的子类，但内部还有一个双向链表维护者键值对的顺序；每一个键值对即位于哈希表中，也存在于这个双向链表中。LinkedHashMap 支持两种顺序：第一种是插入顺序，另外一种是访问顺序。

插入顺序，比较容易理解，先添加的元素在前边，后添加的元素在后边，修改和访问操作并不改变元素在链表中的顺序。那访问顺序是什么意思那？所谓访问指的就是 put/get 操作，对于一个 key 执行 get/put 操作之后，对应的键值对就会移动到链表尾部。所以链表尾部就是最近访问的，最开始的就是最久没被访问的。

因此最简单的方法就是在创建一个 LinkedHashMap 时直接指定访问顺序和容量。此后直接操作 LinkedHashMap 即可。

具体代码如下：

import java.util.LinkedHashMap;
import java.util.Map.Entry;

class LRUCache {
MyLRUCache<Integer,Integer> cache;
   public LRUCache(int capacity) {
   cache = new MyLRUCache(capacity);
   }

public int get(int key) {
       if(cache.get(key) == null) {
           return -1;
       }
   return cache.get(key);
   }

public void put(int key, int value) {
   cache.put(key, value);
   }
}
class MyLRUCache<K,V> extends LinkedHashMap<K,V> {
   private int capacity;
   public MyLRUCache(int capacity) {
       //指定初始容量，增长因子，指定访问顺序
       super(16, 0.75f, true);
       this.capacity = capacity;
   }
           //由于LinkedHahsMap本身是不支持容量限制，我们可以成通过重写removeEldestEntry，使得容量大于预定容量时，删除头部的元素
   @Override
protected boolean removeEldestEntry(Entry<K, V> eldest) {
   return size() > capacity;
}
}

方法三

由于方法二需要通过重写 removeEldestEntry 方法来实现缓存，在面试的时候不容易想到，因此我们考虑只是用 LinkedHashMap 的插入顺序，增加若干操作来实现 LRU 缓存。

class LRUCache {
   int capacity;
   LinkedHashMap<Integer,Integer> cache;
   public LRUCache(int capacity) {
       this.capacity = capacity;
       cache = new LinkedHashMap<>();
   }

public int get(int key) {
       if(!cache.containsKey(key)) {
           return -1;
       }
       makeRecently(key);
       return cache.get(key);
   }

public void put(int key, int value) {
       if(cache.containsKey(key)) {
           //修改value的值
           cache.put(key,value);
           makeRecently(key);
           return;
       }
       if(cache.size() >= this.capacity) {
           //链表头部是最久未被使用的key
           int oldestKey = cache.keySet().iterator().next();
           cache.remove(oldestKey);
       }
       cache.put(key,value);
   }
   private void makeRecently(int key) {
       int val = cache.get(key);
       cache.remove(key);
       cache.put(key,val);
   }
}

总结

本文主要讲了如何通过哈希链表这种数据结构来实现 LRU 算法，提供了三种实现思路，第一种从双向链表开始，借助于 HashMap 来实现满足要求的 LRUCache，后两种针对 LinkedHashMap 的不同顺序，设计了两种实现方式来实现 LRUCache。

来源：https://www.vcjmhg.top/how-write-lru