Java 手寫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 的數據結構應該具有如下特點：
- cache 中的元素必須是具有時序的，這樣才能區分最近使用的和最久未使用的數據
- 在 cache 中能夠快速的通過 key 來找到對應的 val。
- 每次訪問 cache 的某個 key 時需要將這個元素變成最近使用的，也就是說 cache 要支持在任意位置快速插入和刪除元素。
那麼有什麼數據結構同時符合上邊所有的要求那？HashMap 可以根據某個 key 快速定位到對應的 val，但是它不具有時序性（存儲的數據沒有順序）。LinkedList 似乎支持快速插入和刪除元素，而且具有固定順序，但它並不支持快速查找。所以我們可以考慮將兩者結合起來形成一種新的數據結構 LinkedHashMap。
LRU 算法的核心數據結構就是哈希鏈表，它是雙向鏈表和哈希表的結合體。其具體數據結構如下圖所示：
借助這個數據結構我們來註意分析上邊的條件：
- 如果每次默認從鏈表尾部添加元素，那麼顯然越靠近尾部的元素越是最近使用的，越是靠近頭部的元素越是最久未被使用的。
- 對於某一個 key，可以通過哈希表快速定位到對應的 val 上
- 鏈表顯然支持快速插入和快速刪除。
方法一
在 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。
以上就是Java 手寫LRU緩存淘汰算法的詳細內容，更多關於Java 寫LRU緩存淘汰算法的資料請關註WalkonNet其它相關文章！
推薦閱讀：
- Java之理解Redis回收算法LRU案例講解
- 手動實現Redis的LRU緩存機制示例詳解
- 淺談java如何實現Redis的LRU緩存機制
- Java實現常用緩存淘汰算法:FIFO、LRU、LFU
- LRU算法在Vue內置組件keep-alive中的使用