Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU
緩存淘汰算法
在高并發(fā)、高性能的質(zhì)量要求不斷提高時(shí),我們首先會(huì)想到的就是利用緩存予以應(yīng)對(duì)。
第一次請(qǐng)求時(shí)把計(jì)算好的結(jié)果存放在緩存中,下次遇到同樣的請(qǐng)求時(shí),把之前保存在緩存中的數(shù)據(jù)直接拿來(lái)使用。
但是,緩存的空間一般都是有限,不可能把所有的結(jié)果全部保存下來(lái)。那么,當(dāng)緩存空間全部被占滿再有新的數(shù)據(jù)需要被保存,就要決定刪除原來(lái)的哪些數(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)單地說(shuō),先存入緩存的數(shù)據(jù),先被淘汰。
最早存入緩存的數(shù)據(jù),其不再被使用的可能性比剛存入緩存的可能性大。建立一個(gè)FIFO隊(duì)列,記錄所有在緩存中的數(shù)據(jù)。當(dāng)一條數(shù)據(jù)被存入緩存時(shí),就把它插在隊(duì)尾上。需要被淘汰的數(shù)據(jù)一直在隊(duì)列頭。這種算法只是在按線性順序訪問(wèn)數(shù)據(jù)時(shí)才是理想的,否則效率不高。因?yàn)槟切┏1辉L問(wèn)的數(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)單地說(shuō),LRU 的淘汰規(guī)則是基于訪問(wèn)時(shí)間。
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被使用到,那么可以認(rèn)為在將來(lái)它被使用的可能性也很小。因此,當(dāng)緩存空間滿時(shí),最久沒(méi)有使用的數(shù)據(jù)最先被淘汰。
在Java中,其實(shí)LinkedHashMap已經(jīng)實(shí)現(xiàn)了LRU緩存淘汰算法,需要在構(gòu)造函數(shù)第三個(gè)參數(shù)傳入true,表示按照時(shí)間順序訪問(wèn)??梢灾苯永^承LinkedHashMap來(lái)實(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是表示按照訪問(wèn)時(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í)間先后順序。
在訪問(wèn)數(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)單地說(shuō),LFU 的淘汰規(guī)則是基于訪問(wèn)次數(shù)。
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間很少被使用到,那么可以認(rèn)為在將來(lái)它被使用的可能性也很小。因此,當(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ù)的訪問(wèn)頻率 addUsedCount(node); return node.value; } public V put(K key, V value) { Node node = map.get(key); if (node != null) { // 如果存在則增加該數(shù)據(jù)的訪問(wèn)頻次 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)文章
Java介紹多線程計(jì)算階乘實(shí)現(xiàn)方法
這篇文章主要為大家詳細(xì)介紹了Java多線程計(jì)算階乘的實(shí)現(xiàn),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06Java 實(shí)現(xiàn)簡(jiǎn)單靜態(tài)資源Web服務(wù)器的示例
這篇文章主要介紹了Java 實(shí)現(xiàn)簡(jiǎn)單靜態(tài)資源Web服務(wù)器的示例,幫助大家更好的理解和使用Java,感興趣的朋友可以了解下2020-11-11深入了解Java SpringBoot自動(dòng)裝配原理
在使用springboot時(shí),很多配置我們都沒(méi)有做,都是springboot在幫我們完成,這很大一部分歸功于springboot自動(dòng)裝配。本文將詳細(xì)為大家講解SpringBoot的自動(dòng)裝配原理,需要的可以參考一下2022-03-03解決ResourceBundle.getBundle文件路徑問(wèn)題
這篇文章主要介紹了解決ResourceBundle.getBundle文件路徑問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01Java中byte、byte數(shù)組與int、long的轉(zhuǎn)換詳解
這篇文章分別給大家介紹了Java中byte和int之間的轉(zhuǎn)換、Java中 byte數(shù)組和int之間的轉(zhuǎn)換、Java中byte數(shù)組和long之間的轉(zhuǎn)換以及整理了整體工具類的源碼,需要的朋友可以參考借鑒,下面來(lái)一起看看吧。2017-02-02ResultSet如何動(dòng)態(tài)獲取列名和值
這篇文章主要介紹了ResultSet如何動(dòng)態(tài)獲取列名和值問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12java中PriorityBlockingQueue的入隊(duì)知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理一篇關(guān)于java中PriorityBlockingQueue的入隊(duì)知識(shí)點(diǎn)總結(jié)內(nèi)容,有需要的朋友們可以學(xué)習(xí)下。2021-01-01