登录 注册

手写 LRU 缓存淘汰算法

本贴最后更新于 1351 天前，其中的信息可能已经渤澥桑田

概述

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

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

  • LRU 最近最久未使用
  • FIFO 先进先出置换算法 类似队列
  • OPT 最佳置换算法 （理想中存在的）
  • NRU Clock 置换算法
  • LFU 最少使用置换算法
  • PBA 页面缓冲算法

LRU 的原理

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

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

53cb2d05d9bc8e3131466e9802d2c6d3.png

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

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 算法的核心数据结构就是哈希链表，它是双向链表和哈希表的结合体。其具体数据结构如下图所示：

image20210403155130707.png

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

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

image20210403171709788.png

至此，我们已经完全掌握了 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;
	}
}

image20210403165853898.png

方法三

由于方法二需要通过重写 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);
    }
}

image20210403171616299.png

总结

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

引用

  1. https://blog.csdn.net/qq_40050586/article/details/105851970
  2. 《labuladong 的算法小抄》p216 页面
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3190 引用 • 8214 回帖 • 1 关注
  • LRU
    2 引用
成都 位置
264 16 39 77 10 8 113

相关帖子

回帖
手写 LRU 缓存淘汰算法

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
vcjmhg
自律者自由 成都
回帖
49
 帖子
83
 积分
2989