Java 手寫LRU緩存淘汰算法

更新時(shí)間：2021年05月28日 08:59:16 作者：vcjmhg

本文主要講了如何通過哈希鏈表這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)LRU算法，提供了三種實(shí)現(xiàn)思路，第一種從雙向鏈表開始，借助于HashMap來實(shí)現(xiàn)滿足要求的LRUCache

概述

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í)間局部性策略來設(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è)置為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 中能夠快速的通過 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算法必須的API
class 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è)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 本身地址并沒有變化所以不需要重新來維護(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;
    //用來記錄鏈表元素?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è)卦阪湵碇械捻樞?。那訪問順序是什么意思那？所謂訪問指的就是 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í)，刪除頭部的元素
    @Override
	protected 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)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: