Java 手寫LRU緩存淘汰算法

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

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

概述

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

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

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

LRU 的原理

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

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

同樣的，針對一個緩存數(shù)據(jù)，如果其使用的時間越近，那么它被再次使用的概率就越大，反之一個緩存數(shù)據(jù)如果很長時間未被使用，那它會被再次使用的概率就會很小。因而當緩存空間不足時，我們優(yōu)先刪除最久未被使用的緩存數(shù)據(jù)，進而提高緩存命中率。

LRU 算法的實現(xiàn)

LRU 算法描述

緩存在使用時，核心 API 有兩個：

int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

具體使用的例子如下：

//初始化一個緩存，并將緩存空間設置為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)已經(jīng)被刪除，因而返回 -1

LRU 算法代碼實現(xiàn)

分析上面的算法操作，如果想要讓 put 和 get 方法的時間復雜度位 O(1)，cache 的數(shù)據(jù)結構應該具有如下特點：

cache 中的元素必須是具有時序的，這樣才能區(qū)分最近使用的和最久未使用的數(shù)據(jù)
在 cache 中能夠快速的通過 key 來找到對應的 val。
每次訪問 cache 的某個 key 時需要將這個元素變成最近使用的，也就是說 cache 要支持在任意位置快速插入和刪除元素。

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

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

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

如果每次默認從鏈表尾部添加元素，那么顯然越靠近尾部的元素越是最近使用的，越是靠近頭部的元素越是最久未被使用的。
對于某一個 key，可以通過哈希表快速定位到對應的 val 上
鏈表顯然支持快速插入和快速刪除。

方法一

在 Java 中本身是有 LinkedHashMap 這個數(shù)據(jù)結構的，但是為了了解算法的細節(jié)，我們嘗試自己實現(xiàn)一遍 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;
    }
}

//構建一個雙向鏈表，實現(xiàn)一個LRU算法必須的API
class DoubleList{
    //頭尾虛節(jié)點
    private Node head, tail;
    //用來記錄鏈表元素數(shù)量
    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) {
		//具體實現(xiàn)
    }
  
    public void put(int key, int value) {
		//具體實現(xiàn)
    }
}

由于要同時維護一個雙向鏈表 cache 和一個哈希表 map，在編寫的過程中容易漏掉一些操作，因而我們可以**在這兩種數(shù)據(jù)結構的基礎上，抽象出一層 API。**盡量避免 get 和 put 操作直接操作 map 和 cache 的細節(jié)。

//封裝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);
    //從鏈表中刪除節(jié)點
    cache.remove(x);
    //刪除key->x的映射關系
    map.remove(key);
}
//刪除最久未使用元素
private void removeLeastRecently() {
    //刪除鏈表中的第一個節(jié)點
    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) {
    	//該節(jié)點已經(jīng)存在
    	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);
	  //從鏈表中刪除節(jié)點
	  cache.remove(x);
	  //刪除key->x的映射關系
	  map.remove(key);
  }
  //刪除最久未使用元素
  private void removeLeastRecently() {
	  //刪除鏈表中的第一個節(jié)點
	  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;
    }
}
//構建一個雙向鏈表，實現(xiàn)一個LRU算法必須的API
class DoubleList{
    //頭尾虛節(jié)點
    private Node head, tail;
    //用來記錄鏈表元素數(shù)量
    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;
    }
}

至此，我們已經(jīng)完全掌握了 LRU 算法的原理和實現(xiàn)了，最后我們可以通過 Java 內(nèi)置的類型 LinkedHashMap 來實現(xiàn)以下 LRU 算法。

方法二

在正式編寫之前，我們簡單說是說這個 LinkedHashMap。

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

插入順序，比較容易理解，先添加的元素在前邊，后添加的元素在后邊，修改和訪問操作并不改變元素在鏈表中的順序。那訪問順序是什么意思那？所謂訪問指的就是 put/get 操作，對于一個 key 執(zhí)行 get/put 操作之后，對應的鍵值對就會移動到鏈表尾部。所以鏈表尾部就是最近訪問的，最開始的就是最久沒被訪問的。

因此最簡單的方法就是在創(chuàng)建一個 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 方法來實現(xiàn)緩存，在面試的時候不容易想到，因此我們考慮只是用 LinkedHashMap 的插入順序，增加若干操作來實現(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);
    }
}

總結

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

以上就是Java 手寫LRU緩存淘汰算法的詳細內(nèi)容，更多關于Java 寫LRU緩存淘汰算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: