目錄概述LRU 的原理LRU 算法的實(shí)現(xiàn)LRU 算法描述LRU 算法代碼實(shí)現(xiàn)方法一方法二方法三總結(jié)概述

LRU 算法全稱為 Least Recently Used 是一種常見的頁面緩存淘汰算法，當(dāng)緩存空間達(dá)到達(dá)到預(yù)設(shè)空間的情況下會(huì)刪除那些最久沒有被使用的數(shù)據(jù) 。

常見的頁面緩存淘汰算法主要有一下幾種：

LRU 最近最久未使用 FIFO 先進(jìn)先出置換算法 類似隊(duì)列 OPT 最佳置換算法 （理想中存在的） NRU Clock 置換算法 LFU 最少使用置換算法 PBA 頁面緩沖算法 LRU 的原理

LRU 算法的設(shè)計(jì)原理其實(shí)就是計(jì)算機(jī)的 局部性原理（這個(gè) 局部性原理 包含了 空間局部性 和 時(shí)間局部性 兩種策略）。LRU 算法主要是依據(jù) 時(shí)間局部性策略 來設(shè)計(jì)的。

這個(gè)策略簡(jiǎn)單來說就是，如果一個(gè)數(shù)據(jù)被訪問了，那么在短時(shí)間內(nèi)它還會(huì)被訪問。

同樣的，針對(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è)置為2LRUCache cache = new LRUCache(2);cache.put(1,1); // cache = [(1,1)]cache.put(2,2); // cache = [(2,2),(1,1)]cache.get(1); //返回1cache.put(3,3) //cache = [(3,3),(2,2)]，緩存空間已滿，需要?jiǎng)h除空間騰出位置，因而刪除最久未被使用的(1,1)cache.get(1); //返回 -1 因?yàn)?1,1)已經(jīng)被刪除，因而返回 -1LRU 算法代碼實(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 中能夠快速的通過 key 來找到對(duì)應(yīng)的 val。 每次訪問 cache 的某個(gè) key 時(shí)需要將這個(gè)元素變成最近使用的，也就是說 cache 要支持在任意位置快速插入和刪除元素。

那么有什么數(shù)據(jù)結(jié)構(gòu)同時(shí)符合上邊所有的要求那？HashMap 可以根據(jù)某個(gè) key 快速定位到對(duì)應(yīng)的 val，但是它不具有時(shí)序性（存儲(chǔ)的數(shù)據(jù)沒有順序）。LinkedList 似乎支持快速插入和刪除元素，而且具有固定順序，但它并不支持快速查找。所以我們可以考慮將兩者結(jié)合起來形成一種新的數(shù)據(jù)結(jié)構(gòu) LinkedHashMap。

LRU 算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表，它是雙向鏈表和哈希表的結(jié)合體。其具體數(shù)據(jù)結(jié)構(gòu)如下圖所示：

借助這個(gè)數(shù)據(jù)結(jié)構(gòu)我們來注意分析上邊的條件：

如果每次默認(rèn)從鏈表尾部添加元素，那么顯然越靠近尾部的元素越是最近使用的，越是靠近頭部的元素越是最久未被使用的。 對(duì)于某一個(gè) key，可以通過哈希表快速定位到對(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算法必須的APIclass DoubleList{ //頭尾虛節(jié)點(diǎn) private Node head, tail; //用來記錄鏈表元素?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é)合起來就可以打出整個(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，在編寫的過程中容易漏掉一些操作，因而我們可以**在這兩種數(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 本身地址并沒有變化所以不需要重新來維護(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è)keyprivate 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 本身地址并沒有變化所以不需要重新來維護(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算法必須的APIclass DoubleList{ //頭尾虛節(jié)點(diǎn) private Node head, tail; //用來記錄鏈表元素?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)了，最后我們可以通過 Java 內(nèi)置的類型 LinkedHashMap 來實(shí)現(xiàn)以下 LRU 算法。

方法二

在正式編寫之前，我們簡(jiǎn)單說是說這個(gè) LinkedHashMap。

LinkedHashMap 是 HashMap 的子類，但內(nèi)部還有一個(gè)雙向鏈表維護(hù)者鍵值對(duì)的順序；每一個(gè)鍵值對(duì)即位于哈希表中，也存在于這個(gè)雙向鏈表中。LinkedHashMap 支持兩種順序：第一種是插入順序，另外一種是訪問順序。

插入順序，比較容易理解，先添加的元素在前邊，后添加的元素在后邊，修改和訪問操作并不改變?cè)卦阪湵碇械捻樞颉Ｄ窃L問順序是什么意思那？所謂訪問指的就是 put/get 操作，對(duì)于一個(gè) key 執(zhí)行 get/put 操作之后，對(duì)應(yīng)的鍵值對(duì)就會(huì)移動(dòng)到鏈表尾部。所以鏈表尾部就是最近訪問的，最開始的就是最久沒被訪問的。

因此最簡(jiǎn)單的方法就是在創(chuàng)建一個(gè) LinkedHashMap 時(shí)直接指定訪問順序和容量。此后直接操作 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)因子，指定訪問順序super(16, 0.75f, true);this.capacity = capacity; } //由于LinkedHahsMap本身是不支持容量限制，我們可以成通過重寫removeEldestEntry，使得容量大于預(yù)定容量時(shí)，刪除頭部的元素 @Overrideprotected boolean removeEldestEntry(Entry<K, V> eldest) { return size() > capacity;}}

方法三

由于方法二需要通過重寫 removeEldestEntry 方法來實(shí)現(xiàn)緩存，在面試的時(shí)候不容易想到，因此我們考慮只是用 LinkedHashMap 的插入順序，增加若干操作來實(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é)

本文主要講了如何通過哈希鏈表這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) LRU 算法，提供了三種實(shí)現(xiàn)思路，第一種從雙向鏈表開始，借助于 HashMap 來實(shí)現(xiàn)滿足要求的 LRUCache，后兩種針對(duì) LinkedHashMap 的不同順序，設(shè)計(jì)了兩種實(shí)現(xiàn)方式來實(shí)現(xiàn) LRUCache。

以上就是Java 手寫LRU緩存淘汰算法的詳細(xì)內(nèi)容，更多關(guān)于Java 寫LRU緩存淘汰算法的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！