Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU
緩存淘汰算法
在高并發(fā)、高性能的質(zhì)量要求不斷提高時(shí)，我們首先會(huì)想到的就是利用緩存予以應(yīng)對(duì)。
第一次請(qǐng)求時(shí)把計(jì)算好的結(jié)果存放在緩存中，下次遇到同樣的請(qǐng)求時(shí)，把之前保存在緩存中的數(shù)據(jù)直接拿來使用。
但是，緩存的空間一般都是有限，不可能把所有的結(jié)果全部保存下來。那么，當(dāng)緩存空間全部被占滿再有新的數(shù)據(jù)需要被保存，就要決定刪除原來的哪些數(shù)據(jù)。如何做這樣決定需要使用緩存淘汰算法。
常用的緩存淘汰算法有：FIFO、LRU、LFU，下面我們就逐一介紹一下。
FIFO
FIFO，F(xiàn)irst In First Out，先進(jìn)先出算法。判斷被存儲(chǔ)的時(shí)間，離目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說，先存入緩存的數(shù)據(jù)，先被淘汰。
最早存入緩存的數(shù)據(jù)，其不再被使用的可能性比剛存入緩存的可能性大。建立一個(gè)FIFO隊(duì)列，記錄所有在緩存中的數(shù)據(jù)。當(dāng)一條數(shù)據(jù)被存入緩存時(shí)，就把它插在隊(duì)尾上。需要被淘汰的數(shù)據(jù)一直在隊(duì)列頭。這種算法只是在按線性順序訪問數(shù)據(jù)時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的數(shù)據(jù)，往往在緩存中也停留得最久，結(jié)果它們卻因變“老”而不得不被淘汰出去。
FIFO算法用隊(duì)列實(shí)現(xiàn)就可以了，這里就不做代碼實(shí)現(xiàn)了。
LRU
LRU，Least Recently Used，最近最少使用算法。判斷最近被使用的時(shí)間，目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說，LRU 的淘汰規(guī)則是基于訪問時(shí)間。
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒有被使用到，那么可以認(rèn)為在將來它被使用的可能性也很小。因此，當(dāng)緩存空間滿時(shí)，最久沒有使用的數(shù)據(jù)最先被淘汰。
在Java中，其實(shí)LinkedHashMap已經(jīng)實(shí)現(xiàn)了LRU緩存淘汰算法，需要在構(gòu)造函數(shù)第三個(gè)參數(shù)傳入true，表示按照時(shí)間順序訪問。可以直接繼承LinkedHashMap來實(shí)現(xiàn)。
package one.more;
import java.util.LinkedHashMap;
import java.util.Map;
public class LruCache<K, V> extends LinkedHashMap<K, V> {
/**
* 容量限制
*/
private int capacity;
LruCache(int capacity) {
// 初始大小，0.75是裝載因子，true是表示按照訪問時(shí)間排序
super(capacity, 0.75f, true);
//緩存最大容量
this.capacity = capacity;
}
/**
* 重寫removeEldestEntry方法，如果緩存滿了，則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
我寫一個(gè)簡(jiǎn)單的程序測(cè)試一下：
package one.more;
public class TestApp {
public static void main(String[] args) {
LruCache<String, String> cache = new LruCache(3);
cache.put("keyA", "valueA");
System.out.println("put keyA");
System.out.println(cache);
System.out.println("=========================");
cache.put("keyB", "valueB");
System.out.println("put keyB");
System.out.println(cache);
System.out.println("=========================");
cache.put("keyC", "valueC");
System.out.println("put keyC");
System.out.println(cache);
System.out.println("=========================");
cache.get("keyA");
System.out.println("get keyA");
System.out.println(cache);
System.out.println("=========================");
cache.put("keyD", "valueD");
System.out.println("put keyD");
System.out.println(cache);
}
}
運(yùn)行結(jié)果如下：
put keyA
{keyA=valueA}
=========================
put keyB
{keyA=valueA, keyB=valueB}
=========================
put keyC
{keyA=valueA, keyB=valueB, keyC=valueC}
=========================
get keyA
{keyB=valueB, keyC=valueC, keyA=valueA}
=========================
put keyD
{keyC=valueC, keyA=valueA, keyD=valueD}
當(dāng)然，這個(gè)不是面試官想要的，也不是我們想要的。我們可以使用雙向鏈表和哈希表進(jìn)行實(shí)現(xiàn)，哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)，雙向鏈表用于數(shù)據(jù)被使用的時(shí)間先后順序。
在訪問數(shù)據(jù)時(shí)，如果數(shù)據(jù)已存在緩存中，則把該數(shù)據(jù)的對(duì)應(yīng)節(jié)點(diǎn)移到鏈表尾部。如此操作，在鏈表頭部的節(jié)點(diǎn)則是最近最少使用的數(shù)據(jù)。
當(dāng)需要添加新的數(shù)據(jù)到緩存時(shí)，如果該數(shù)據(jù)已存在緩存中，則把該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)移到鏈表尾部；如果不存在，則新建一個(gè)對(duì)應(yīng)的節(jié)點(diǎn)，放到鏈表尾部；如果緩存滿了，則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。
package one.more;
import java.util.HashMap;
import java.util.Map;
public class LruCache<K, V> {
/**
* 頭結(jié)點(diǎn)
*/
private Node head;
/**
* 尾結(jié)點(diǎn)
*/
private Node tail;
/**
* 容量限制
*/
private int capacity;
/**
* key和數(shù)據(jù)的映射
*/
private Map<K, Node> map;
LruCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
}
public V put(K key, V value) {
Node node = map.get(key);
// 數(shù)據(jù)存在，將節(jié)點(diǎn)移動(dòng)到隊(duì)尾
if (node != null) {
V oldValue = node.value;
//更新數(shù)據(jù)
node.value = value;
moveToTail(node);
return oldValue;
} else {
Node newNode = new Node(key, value);
// 數(shù)據(jù)不存在，判斷鏈表是否滿
if (map.size() == capacity) {
// 如果滿，則刪除隊(duì)首節(jié)點(diǎn)，更新哈希表
map.remove(removeHead().key);
}
// 放入隊(duì)尾節(jié)點(diǎn)
addToTail(newNode);
map.put(key, newNode);
return null;
}
}
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveToTail(node);
return node.value;
}
return null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LruCache{");
Node curr = this.head;
while (curr != null) {
if(curr != this.head){
sb.append(',').append(' ');
}
sb.append(curr.key);
sb.append('=');
sb.append(curr.value);
curr = curr.next;
}
return sb.append('}').toString();
}
private void addToTail(Node newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
//連接新節(jié)點(diǎn)
tail.next = newNode;
newNode.pre = tail;
//更新尾節(jié)點(diǎn)指針為新節(jié)點(diǎn)
tail = newNode;
}
}
private void moveToTail(Node node) {
if (tail == node) {
return;
}
if (head == node) {
head = node.next;
head.pre = null;
} else {
//調(diào)整雙向鏈表指針
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
private Node removeHead() {
if (head == null) {
return null;
}
Node res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
class Node {
K key;
V value;
Node pre;
Node next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
再次運(yùn)行測(cè)試程序，結(jié)果如下：
put keyA
LruCache{keyA=valueA}
=========================
put keyB
LruCache{keyA=valueA, keyB=valueB}
=========================
put keyC
LruCache{keyA=valueA, keyB=valueB, keyC=valueC}
=========================
get keyA
LruCache{keyB=valueB, keyC=valueC, keyA=valueA}
=========================
put keyD
LruCache{keyC=valueC, keyA=valueA, keyD=valueD}
LFU
LFU，Least Frequently Used，最不經(jīng)常使用算法，在一段時(shí)間內(nèi)，數(shù)據(jù)被使用次數(shù)最少的，優(yōu)先被淘汰。簡(jiǎn)單地說，LFU 的淘汰規(guī)則是基于訪問次數(shù)。
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間很少被使用到，那么可以認(rèn)為在將來它被使用的可能性也很小。因此，當(dāng)空間滿時(shí)，最小頻率使用的數(shù)據(jù)最先被淘汰。
我們可以使用雙哈希表進(jìn)行實(shí)現(xiàn)，一個(gè)哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)，另一個(gè)哈希表用于存儲(chǔ)數(shù)據(jù)被使用次數(shù)和對(duì)應(yīng)的數(shù)據(jù)。
package one.more;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class LfuCache<K, V> {
/**
* 容量限制
*/
private int capacity;
/**
* 當(dāng)前最小使用次數(shù)
*/
private int minUsedCount;
/**
* key和數(shù)據(jù)的映射
*/
private Map<K, Node> map;
/**
* 數(shù)據(jù)頻率和對(duì)應(yīng)數(shù)據(jù)組成的鏈表
*/
private Map<Integer, List<Node>> usedCountMap;
public LfuCache(int capacity) {
this.capacity = capacity;
this.minUsedCount = 1;
this.map = new HashMap<>();
this.usedCountMap = new HashMap<>();
}
public V get(K key) {
Node node = map.get(key);
if (node == null) {
return null;
}
// 增加數(shù)據(jù)的訪問頻率
addUsedCount(node);
return node.value;
}
public V put(K key, V value) {
Node node = map.get(key);
if (node != null) {
// 如果存在則增加該數(shù)據(jù)的訪問頻次
V oldValue = node.value;
node.value = value;
addUsedCount(node);
return oldValue;
} else {
// 數(shù)據(jù)不存在，判斷鏈表是否滿
if (map.size() == capacity) {
// 如果滿，則刪除隊(duì)首節(jié)點(diǎn)，更新哈希表
List<Node> list = usedCountMap.get(minUsedCount);
Node delNode = list.get(0);
list.remove(delNode);
map.remove(delNode.key);
}
// 新增數(shù)據(jù)并放到數(shù)據(jù)頻率為1的數(shù)據(jù)鏈表中
Node newNode = new Node(key, value);
map.put(key, newNode);
List<Node> list = usedCountMap.get(1);
if (list == null) {
list = new LinkedList<>();
usedCountMap.put(1, list);
}
list.add(newNode);
minUsedCount = 1;
return null;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("LfuCache{");
List<Integer> usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());
usedCountList.sort(Comparator.comparingInt(i -> i));
int count = 0;
for (int usedCount : usedCountList) {
List<Node> list = this.usedCountMap.get(usedCount);
if (list == null) {
continue;
}
for (Node node : list) {
if (count > 0) {
sb.append(',').append(' ');
}
sb.append(node.key);
sb.append('=');
sb.append(node.value);
sb.append("(UsedCount:");
sb.append(node.usedCount);
sb.append(')');
count++;
}
}
return sb.append('}').toString();
}
private void addUsedCount(Node node) {
List<Node> oldList = usedCountMap.get(node.usedCount);
oldList.remove(node);
// 更新最小數(shù)據(jù)頻率
if (minUsedCount == node.usedCount && oldList.isEmpty()) {
minUsedCount++;
}
node.usedCount++;
List<Node> set = usedCountMap.get(node.usedCount);
if (set == null) {
set = new LinkedList<>();
usedCountMap.put(node.usedCount, set);
}
set.add(node);
}
class Node {
K key;
V value;
int usedCount = 1;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
再次運(yùn)行測(cè)試程序，結(jié)果如下：
put keyA
LfuCache{keyA=valueA(UsedCount:1)}
=========================
put keyB
LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}
=========================
put keyC
LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}
=========================
get keyA
LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}
=========================
put keyD
LfuCache{keyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)}
總結(jié)
看到這里，你已經(jīng)超越了大多數(shù)人！
FIFO，F(xiàn)irst In First Out，先進(jìn)先出算法。判斷被存儲(chǔ)的時(shí)間，離目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰，可以使用隊(duì)列實(shí)現(xiàn)。
LRU，Least Recently Used，最近最少使用算法。判斷最近被使用的時(shí)間，目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰，可以使用雙向鏈表和哈希表實(shí)現(xiàn)。
LFU，Least Frequently Used，最不經(jīng)常使用算法，在一段時(shí)間內(nèi)，數(shù)據(jù)被使用次數(shù)最少的，優(yōu)先被淘汰，可以使用雙哈希表實(shí)現(xiàn)。
以上就是Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU的詳細(xì)內(nèi)容，更多關(guān)于Java緩存淘汰算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了Jedis對(duì)redis的五大操作代碼詳解，分別是字符串、列表、散列、集合、有序集合，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
SpringMVC攔截器實(shí)現(xiàn)監(jiān)聽session是否過期詳解
這篇文章主要介紹了SpringMVC攔截器實(shí)現(xiàn)監(jiān)聽session是否過期詳解，還是比較不錯(cuò)的，這里分享給大家，供需要的朋友參考。2017-11-11
java用兩個(gè)例子充分闡述多態(tài)的可拓展性介紹
下面小編就為大家?guī)硪黄猨ava用兩個(gè)例子充分闡述多態(tài)的可拓展性介紹。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06
教你如何編寫簡(jiǎn)單的網(wǎng)絡(luò)爬蟲
實(shí)際的爬蟲是從一系列的種子鏈接開始。種子鏈接是起始節(jié)點(diǎn)，種子頁面的超鏈接指向的頁面是子節(jié)點(diǎn)（中間節(jié)點(diǎn)），對(duì)于非html文檔，如excel等，不能從中提取超鏈接，看做圖的終端節(jié)點(diǎn)2013-10-10
這篇文章主要介紹了Java中Http連接的兩種方式(小結(jié))，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
java字符串的替換replace、replaceAll、replaceFirst的區(qū)別說明
這篇文章主要介紹了java字符串的替換replace、replaceAll、replaceFirst的區(qū)別說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
今天小編就為大家分享一篇關(guān)于spring循環(huán)注入異常問題的解決方案，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
從入門到精通詳解SpringBoot中請(qǐng)求參數(shù)注解的完全指南
我們應(yīng)該如何在后端優(yōu)雅地接收這些參數(shù),Spring?Boot提供了一系列注解來幫助我們輕松完成請(qǐng)求參數(shù)的綁定,本文將對(duì)其中最常用的注解進(jìn)行詳細(xì)講解,包括它們的用法、區(qū)別以及最佳實(shí)踐2026-05-05
解決SpringBoot中使用@Transactional注解遇到的問題
這篇文章主要介紹了SpringBoot中使用@Transactional注解遇到的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
Java中實(shí)現(xiàn)時(shí)間偏移(Time?Offset)處理過程
本文介紹Java中時(shí)間偏移處理,利用java.time包中的ZonedDateTime、ZoneOffset等類,支持跨時(shí)區(qū)轉(zhuǎn)換、日志統(tǒng)一標(biāo)準(zhǔn),并給出最佳實(shí)踐中注意事項(xiàng)與應(yīng)用場(chǎng)景示例2025-09-09