Java 手寫LRU緩存淘汰算法
概述
LRU 算法全稱為 Least Recently Used 是一種常見的頁(yè)面緩存淘汰算法，當(dāng)緩存空間達(dá)到達(dá)到預(yù)設(shè)空間的情況下會(huì)刪除那些最久沒有被使用的數(shù)據(jù) 。
常見的頁(yè)面緩存淘汰算法主要有一下幾種：
- LRU 最近最久未使用
- FIFO 先進(jìn)先出置換算法 類似隊(duì)列
- OPT 最佳置換算法 （理想中存在的）
- NRU Clock 置換算法
- LFU 最少使用置換算法
- PBA 頁(yè)面緩沖算法
LRU 的原理
LRU 算法的設(shè)計(jì)原理其實(shí)就是計(jì)算機(jī)的 局部性原理（這個(gè) 局部性原理 包含了 空間局部性 和 時(shí)間局部性 兩種策略）。LRU 算法主要是依據(jù) 時(shí)間局部性策略 來(lái)設(shè)計(jì)的。
這個(gè)策略簡(jiǎn)單來(lái)說(shuō)就是，如果一個(gè)數(shù)據(jù)被訪問(wèn)了，那么在短時(shí)間內(nèi)它還會(huì)被訪問(wèn)。
同樣的，針對(duì)一個(gè)緩存數(shù)據(jù)，如果其使用的時(shí)間越近，那么它被再次使用的概率就越大，反之一個(gè)緩存數(shù)據(jù)如果很長(zhǎng)時(shí)間未被使用，那它會(huì)被再次使用的概率就會(huì)很小。因而當(dāng)緩存空間不足時(shí)，我們優(yōu)先刪除最久未被使用的緩存數(shù)據(jù)，進(jìn)而提高緩存命中率。
LRU 算法的實(shí)現(xiàn)
LRU 算法描述
緩存在使用時(shí)，核心 API 有兩個(gè)：
- int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
- void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
具體使用的例子如下：
//初始化一個(gè)緩存，并將緩存空間設(shè)置為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)]，緩存空間已滿，需要?jiǎng)h除空間騰出位置，因而刪除最久未被使用的(1,1) cache.get(1); //返回 -1 因?yàn)?1,1)已經(jīng)被刪除，因而返回 -1
LRU 算法代碼實(shí)現(xiàn)
分析上面的算法操作，如果想要讓 put 和 get 方法的時(shí)間復(fù)雜度位 O(1)，cache 的數(shù)據(jù)結(jié)構(gòu)應(yīng)該具有如下特點(diǎn)：
- cache 中的元素必須是具有時(shí)序的，這樣才能區(qū)分最近使用的和最久未使用的數(shù)據(jù)
- 在 cache 中能夠快速的通過(guò) key 來(lái)找到對(duì)應(yīng)的 val。
- 每次訪問(wèn) cache 的某個(gè) key 時(shí)需要將這個(gè)元素變成最近使用的，也就是說(shuō) cache 要支持在任意位置快速插入和刪除元素。
那么有什么數(shù)據(jù)結(jié)構(gòu)同時(shí)符合上邊所有的要求那？HashMap 可以根據(jù)某個(gè) key 快速定位到對(duì)應(yīng)的 val，但是它不具有時(shí)序性（存儲(chǔ)的數(shù)據(jù)沒有順序）。LinkedList 似乎支持快速插入和刪除元素，而且具有固定順序，但它并不支持快速查找。所以我們可以考慮將兩者結(jié)合起來(lái)形成一種新的數(shù)據(jù)結(jié)構(gòu) LinkedHashMap。
LRU 算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表，它是雙向鏈表和哈希表的結(jié)合體。其具體數(shù)據(jù)結(jié)構(gòu)如下圖所示：
借助這個(gè)數(shù)據(jù)結(jié)構(gòu)我們來(lái)注意分析上邊的條件：
- 如果每次默認(rèn)從鏈表尾部添加元素，那么顯然越靠近尾部的元素越是最近使用的，越是靠近頭部的元素越是最久未被使用的。
- 對(duì)于某一個(gè) key，可以通過(guò)哈希表快速定位到對(duì)應(yīng)的 val 上
- 鏈表顯然支持快速插入和快速刪除。
方法一
在 Java 中本身是有 LinkedHashMap 這個(gè)數(shù)據(jù)結(jié)構(gòu)的，但是為了了解算法的細(xì)節(jié)，我們嘗試自己實(shí)現(xiàn)一遍 LRU 算法。
首先我們需要定義一個(gè)雙向鏈表，為了簡(jiǎn)化，key 和 val 都設(shè)置稱 int 類型。
class Node {
public int key,val;
public Node next, pre;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
//構(gòu)建一個(gè)雙向鏈表，實(shí)現(xiàn)一個(gè)LRU算法必須的API
class DoubleList{
//頭尾虛節(jié)點(diǎn)
private Node head, tail;
//用來(lái)記錄鏈表元素?cái)?shù)量
private int size;
//初始化鏈表
public DoubleList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.pre = head;
size = 0;
}
//從尾部添加一個(gè)元素
public Node addLast(Node x) {
x.pre = tail.pre;
x.next = tail;
tail.pre.next = x;
tail.pre = x;
size++;
return x;
}
//刪除某一個(gè)元素(x必定存在于雙向鏈表中)
public Node remove(Node x) {
x.pre.next = x.next;
x.next.pre = x.pre;
size--;
return x;
}
//刪除第一個(gè)元素
public Node removeFirst() {
//判斷當(dāng)前size是否為空
if(head.next == tail) {
return null;
}
return remove(head.next);
}
//返回鏈表長(zhǎng)度
public int size() {
return this.size;
}
}
有了雙向鏈表，只需要在 LRU 算法的基礎(chǔ)上把它和 HashMap 結(jié)合起來(lái)就可以打出整個(gè)算法的一個(gè)基本框架。
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) {
//具體實(shí)現(xiàn)
}
public void put(int key, int value) {
//具體實(shí)現(xiàn)
}
}
由于要同時(shí)維護(hù)一個(gè)雙向鏈表 cache 和一個(gè)哈希表 map，在編寫的過(guò)程中容易漏掉一些操作，因而我們可以**在這兩種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，抽象出一層 API。**盡量避免 get 和 put 操作直接操作 map 和 cache 的細(xì)節(jié)。
//封裝HashMap和鏈表組合在一起常用的一些操作
//將某一個(gè)key提升為最近使用
private void makeRecently(int key) {
// ????? 不需要對(duì)map中key和Node的映射關(guān)系進(jìn)行維護(hù)嗎？
//cache 本身地址并沒有變化所以不需要重新來(lái)維護(hù)key和Node的關(guān)系
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);
}
//刪除某一個(gè)key
private void deleteKey(int key) {
Node x = map.get(key);
//從鏈表中刪除節(jié)點(diǎn)
cache.remove(x);
//刪除key->x的映射關(guān)系
map.remove(key);
}
//刪除最久未使用元素
private void removeLeastRecently() {
//刪除鏈表中的第一個(gè)節(jié)點(diǎn)
Node deleteNode = cache.removeFirst();
//刪除map中的映射關(guān)系
map.remove(deleteNode.key);
}
進(jìn)而我們便可以寫出完整的代碼：
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) {
//該節(jié)點(diǎn)已經(jīng)存在
if(map.containsKey(key)) {
deleteKey(key);
addRecently(key, value);
return;
}
if(capacity == cache.size()) {
removeLeastRecently();
}
//添加為最近使用的元素
addRecently(key, value);
}
//封裝HashMap和鏈表組合在一起常用的一些操作
//將某一個(gè)key提升為最近使用
private void makeRecently(int key) {
// ????? 不需要對(duì)map中key和Node的映射關(guān)系進(jìn)行維護(hù)嗎？
//cache 本身地址并沒有變化所以不需要重新來(lái)維護(hù)key和Node的關(guān)系
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);
}
//刪除某一個(gè)key
private void deleteKey(int key) {
Node x = map.get(key);
//從鏈表中刪除節(jié)點(diǎn)
cache.remove(x);
//刪除key->x的映射關(guān)系
map.remove(key);
}
//刪除最久未使用元素
private void removeLeastRecently() {
//刪除鏈表中的第一個(gè)節(jié)點(diǎn)
Node deleteNode = cache.removeFirst();
//刪除map中的映射關(guān)系
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;
}
}
//構(gòu)建一個(gè)雙向鏈表，實(shí)現(xiàn)一個(gè)LRU算法必須的API
class DoubleList{
//頭尾虛節(jié)點(diǎn)
private Node head, tail;
//用來(lái)記錄鏈表元素?cái)?shù)量
private int size;
//初始化鏈表
public DoubleList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.pre = head;
size = 0;
}
//從尾部添加一個(gè)元素
public Node addLast(Node x) {
x.pre = tail.pre;
x.next = tail;
tail.pre.next = x;
tail.pre = x;
size++;
return x;
}
//刪除某一個(gè)元素(x必定存在于雙向鏈表中)
public Node remove(Node x) {
x.pre.next = x.next;
x.next.pre = x.pre;
size--;
return x;
}
//刪除第一個(gè)元素
public Node removeFirst() {
//判斷當(dāng)前size是否為空
if(head.next == tail) {
return null;
}
return remove(head.next);
}
//返回鏈表長(zhǎng)度
public int size() {
return this.size;
}
}
至此，我們已經(jīng)完全掌握了 LRU 算法的原理和實(shí)現(xiàn)了，最后我們可以通過(guò) Java 內(nèi)置的類型 LinkedHashMap 來(lái)實(shí)現(xiàn)以下 LRU 算法。
方法二
在正式編寫之前，我們簡(jiǎn)單說(shuō)是說(shuō)這個(gè) LinkedHashMap。
LinkedHashMap 是 HashMap 的子類，但內(nèi)部還有一個(gè)雙向鏈表維護(hù)者鍵值對(duì)的順序；每一個(gè)鍵值對(duì)即位于哈希表中，也存在于這個(gè)雙向鏈表中。LinkedHashMap 支持兩種順序：第一種是插入順序，另外一種是訪問(wèn)順序。
插入順序，比較容易理解，先添加的元素在前邊，后添加的元素在后邊，修改和訪問(wèn)操作并不改變?cè)卦阪湵碇械捻樞?。那訪問(wèn)順序是什么意思那？所謂訪問(wèn)指的就是 put/get 操作，對(duì)于一個(gè) key 執(zhí)行 get/put 操作之后，對(duì)應(yīng)的鍵值對(duì)就會(huì)移動(dòng)到鏈表尾部。所以鏈表尾部就是最近訪問(wèn)的，最開始的就是最久沒被訪問(wèn)的。
因此最簡(jiǎn)單的方法就是在創(chuàng)建一個(gè) LinkedHashMap 時(shí)直接指定訪問(wèn)順序和容量。此后直接操作 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) {
//指定初始容量，增長(zhǎng)因子，指定訪問(wèn)順序
super(16, 0.75f, true);
this.capacity = capacity;
}
//由于LinkedHahsMap本身是不支持容量限制，我們可以成通過(guò)重寫removeEldestEntry，使得容量大于預(yù)定容量時(shí)，刪除頭部的元素
@Override
protected boolean removeEldestEntry(Entry<K, V> eldest) {
return size() > capacity;
}
}
方法三
由于方法二需要通過(guò)重寫 removeEldestEntry 方法來(lái)實(shí)現(xiàn)緩存，在面試的時(shí)候不容易想到，因此我們考慮只是用 LinkedHashMap 的插入順序，增加若干操作來(lái)實(shí)現(xiàn) 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);
}
}
總結(jié)
本文主要講了如何通過(guò)哈希鏈表這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn) LRU 算法，提供了三種實(shí)現(xiàn)思路，第一種從雙向鏈表開始，借助于 HashMap 來(lái)實(shí)現(xiàn)滿足要求的 LRUCache，后兩種針對(duì) LinkedHashMap 的不同順序，設(shè)計(jì)了兩種實(shí)現(xiàn)方式來(lái)實(shí)現(xiàn) LRUCache。
以上就是Java 手寫LRU緩存淘汰算法的詳細(xì)內(nèi)容，更多關(guān)于Java 寫LRU緩存淘汰算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Eclipse是用java的同行必不可少的工具，我總結(jié)了一下它的快捷鍵，太常用的ctrl+單擊、ctrl+shift+F、Ctrl+1等我就不細(xì)說(shuō)了，主要是方便查看。下邊小編就詳細(xì)的為大家介紹一下2013-07-07
Java自定義簡(jiǎn)單標(biāo)簽實(shí)例
Java自定義簡(jiǎn)單標(biāo)簽可以方便的在頁(yè)面輸出信息，并且對(duì)于權(quán)限的控制，和對(duì)于Jsp標(biāo)簽和servlet代碼的分離有著很好的作用2013-07-07
java基于正則提取字符串中的數(shù)字功能【如提取短信中的驗(yàn)證碼】
這篇文章主要介紹了java基于正則提取字符串中的數(shù)字功能,可用于提取短信中的驗(yàn)證碼,涉及java基于正則的字符串匹配相關(guān)操作技巧,需要的朋友可以參考下2017-01-01
解決Springboot配置excludePathPatterns不生效的問(wèn)題
這篇文章主要介紹了解決Springboot配置excludePathPatterns不生效的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10
這篇文章主要介紹了Java日期與時(shí)間類原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
JAVA實(shí)現(xiàn)網(wǎng)絡(luò)/本地圖片轉(zhuǎn)BASE64存儲(chǔ)代碼示例
這篇文章主要給大家介紹了關(guān)于JAVA實(shí)現(xiàn)網(wǎng)絡(luò)/本地圖片轉(zhuǎn)BASE64存儲(chǔ)的相關(guān)資料,Base64是網(wǎng)絡(luò)上最常見的用于傳輸8Bit字節(jié)碼的編碼方式之一,Base64就是一種基于64個(gè)可打印字符來(lái)表示二進(jìn)制數(shù)據(jù)的方法,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了RabbitMQ?Stream插件使用案例代碼,2.4版為RabbitMQ流插件引入了對(duì)RabbitMQStream插件Java客戶端的初始支持,需要的朋友可以參考下2024-04-04
Java?awt-對(duì)話框簡(jiǎn)單實(shí)現(xiàn)方式
這篇文章主要介紹了Java?awt-對(duì)話框簡(jiǎn)單實(shí)現(xiàn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
使用@RequestBody傳對(duì)象參數(shù)時(shí)碰到的坑
這篇文章主要介紹了使用@RequestBody傳對(duì)象參數(shù)時(shí)碰到的坑，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
解決springboot+thymeleaf視圖映射報(bào)錯(cuò)There?was?an?unexpected?erro
這篇文章主要介紹了解決springboot+thymeleaf視圖映射報(bào)錯(cuò)There?was?an?unexpected?error?(type=Not?Found,?status=404)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12