緩存淘汰算法
在高并發(fā)痴突、高性能的質量要求不斷提高時，我們首先會想到的就是利用緩存予以應對菱涤。
第一次請求時把計算好的結果存放在緩存中苞也，下次遇到同樣的請求時洛勉，把之前保存在緩存中的數(shù)據(jù)直接拿來使用粘秆。
但是，緩存的空間一般都是有限收毫，不可能把所有的結果全部保存下來攻走。那么，當緩存空間全部被占滿再有新的數(shù)據(jù)需要被保存此再，就要決定刪除原來的哪些數(shù)據(jù)昔搂。如何做這樣決定需要使用緩存淘汰算法。
常用的緩存淘汰算法有：FIFO输拇、LRU摘符、LFU，下面我們就逐一介紹一下策吠。
FIFO
FIFO逛裤，First In First Out，先進先出算法猴抹。判斷被存儲的時間带族，離目前最遠的數(shù)據(jù)優(yōu)先被淘汰。簡單地說蟀给，先存入緩存的數(shù)據(jù)蝙砌，先被淘汰。
最早存入緩存的數(shù)據(jù)跋理，其不再被使用的可能性比剛存入緩存的可能性大择克。建立一個FIFO隊列，記錄所有在緩存中的數(shù)據(jù)前普。當一條數(shù)據(jù)被存入緩存時肚邢，就把它插在隊尾上。需要被淘汰的數(shù)據(jù)一直在隊列頭汁政。這種算法只是在按線性順序訪問數(shù)據(jù)時才是理想的道偷，否則效率不高。因為那些常被訪問的數(shù)據(jù)记劈，往往在緩存中也停留得最久勺鸦，結果它們卻因變“老”而不得不被淘汰出去。
FIFO 算法用隊列實現(xiàn)就可以了目木，這里就不做代碼實現(xiàn)了换途。
LRU
LRU懊渡，Least Recently Used，最近最少使用算法军拟。判斷最近被使用的時間剃执，目前最遠的數(shù)據(jù)優(yōu)先被淘汰。簡單地說懈息，LRU 的淘汰規(guī)則是基于訪問時間肾档。
如果一個數(shù)據(jù)在最近一段時間沒有被使用到，那么可以認為在將來它被使用的可能性也很小辫继。因此怒见，當緩存空間滿時，最久沒有使用的數(shù)據(jù)最先被淘汰姑宽。
在Java中遣耍，其實LinkedHashMap已經(jīng)實現(xiàn)了LRU緩存淘汰算法，需要在構造函數(shù)第三個參數(shù)傳入true炮车，表示按照時間順序訪問舵变。可以直接繼承LinkedHashMap來實現(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是表示按照訪問時間排序
super(capacity, 0.75f, true);
//緩存最大容量
this.capacity = capacity;
}
/**
* 重寫removeEldestEntry方法难审，如果緩存滿了瘫拣，則把鏈表頭部第一個節(jié)點和對應的數(shù)據(jù)刪除。
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
寫一個簡單的程序測試一下：
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);
}
}
運行結果如下：
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}
當然告喊，這個不是面試官想要的麸拄，也不是我們想要的。我們可以使用雙向鏈表和哈希表進行實現(xiàn)黔姜，哈希表用于存儲對應的數(shù)據(jù)拢切，雙向鏈表用于數(shù)據(jù)被使用的時間先后順序。
在訪問數(shù)據(jù)時秆吵，如果數(shù)據(jù)已存在緩存中淮椰，則把該數(shù)據(jù)的對應節(jié)點移到鏈表尾部。如此操作纳寂，在鏈表頭部的節(jié)點則是最近最少使用的數(shù)據(jù)主穗。
當需要添加新的數(shù)據(jù)到緩存時，如果該數(shù)據(jù)已存在緩存中毙芜，則把該數(shù)據(jù)對應的節(jié)點移到鏈表尾部忽媒；如果不存在，則新建一個對應的節(jié)點腋粥，放到鏈表尾部晦雨；如果緩存滿了架曹，則把鏈表頭部第一個節(jié)點和對應的數(shù)據(jù)刪除。
