時間緩存演算法
緩存這個東西就是為了提高運行速度的，由於緩存是在寸土寸金的內存裡面，不是在硬碟
裡面，所以容量是很有限的。LRU這個演算法就是把最近一次使用時間離現在時間最遠的數據刪除掉。先說說List：每次訪問一個元素後把這個元素放在
List一端，這樣一來最遠使用的元素自然就被放到List的另一端。緩存滿了t的時候就把那最遠使用的元素remove掉。但更實用的是
HashMap。因為List太慢，要刪掉的數據總是位於List底層數組的第一個位置，刪掉之後，後面的數據要向前補位。。所以復雜度是O(n)，那就
用鏈表結構的LinkedHashMap唄~，LinkedHashMap默認的元素順序是put的順序，但是如果使用帶參數的構造函數，那麼
LinkedHashMap會根據訪問順序來調整內部 順序。
LinkedHashMap的get()方法除了返回元素之外還可以把被訪問的元素放到鏈表的底端，這樣一來每次頂端的元素就是remove的元素。
構造函數如下：
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；
initialCapacity 初始容量
loadFactor 載入因子，一般是 0.75f
accessOrder false 基於插入順序 true 基於訪問順序（get一個元素後，這個元素被加到最後，使用了LRU 最近最少被使用的調度演算法）
來個例子吧：
import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//現在遍歷的話順序肯定是9,7,5,3
//下面訪問了一下9,3這個鍵值對，輸出順序就變嘍~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出
7
5
3
9
好玩吧~
下面開始實現LRU緩存嘍~
import java.util.*;
//擴展一下LinkedHashMap這個類，讓他實現LRU演算法
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{
//定義緩存的容量
private int capacity;
private static final long serialVersionUID = 1L;
//帶參數的構造器
LRULinkedHashMap(int capacity){
//調用LinkedHashMap的構造器，傳入以下參數
super(16,0.75f,true);
//傳入指定的緩存最大容量
this.capacity=capacity;
}
//實現LRU的關鍵方法，如果map裡面的元素個數大於了緩存最大容量，則刪除鏈表的頂端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
}
//測試類
class Test{
public static void main(String[] args) throws Exception{
//指定緩存最大容量為4
Map<Integer,Integer> map=new LRULinkedHashMap<>(4);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
map.put(6,6);
//總共put了5個元素，超過了指定的緩存最大容量
//遍歷結果
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出結果如下
9=3
9=3
9=3
9=3
9=3
7
5
3
6
分析一下：使用帶參數構造器，且啟用LRU模式的LinkedHashMap會在每次有新元素加入的時候，判斷當前儲存元素是否超過了緩存上限，也就是執行
一次removeEldestEntry方法，看最後的遍歷結果，發現果然把9刪除了，LRU發揮作用了~
㈡ 什麼是緩存及一級緩存，二級緩存
緩存：通常人們所說的Cache就是指緩存SRAM。 SRAM叫靜態內存，「靜態」指的是當我們將一筆數據寫入SRAM後，除非重新寫入新數據或關閉電源，否則寫入的數據保持不變。
由於CPU的速度比內存和硬碟的速度要快得多，所以在存取數據時會使CPU等待，影響計算機的速度。SRAM的存取速度比其它內存和硬碟都要快，所以它被用作電腦的高速緩存(Cache)。
有了高速緩存，可以先把數據預寫到其中，需要時直接從它讀出，這就縮短了CPU的等待時間。高速緩存之所以能提高系統的速度是基於一種統計規律，主板上的控制系統會自動統計內存中哪些數據會被頻繁的使用，就把這些數據存在高速緩存中，CPU要訪問這些數據時，就會先到Cache中去找，從而提高整體的運行速度。一般說來，256K的高速緩存能使整機速度平均提高10%左右。
主板上通常都會提供256K到1M的緩存。在CPU內部也有高速緩存，如486CPU有8K的高速緩存，Pentium有16K的高速緩存。Pentium II有32K 一級緩存，AMD K6-2中有64K的一級Cache，AMD K6-3中有64K 的一級 Cache，和256K 的二級 Cache，Cyrix MII 中有64K的Cache。
為了區分它們，CPU內部的緩存叫內部高速緩存(Internal Cache)或一級高速緩存，主板上的緩存叫外部高速緩存(External Cache)或二級高速緩存。不過現在的Pentium II 的CPU已經將主板上的二級緩存封裝在CPU的盒子中，AMD K6-3的CPU內部也集成了256K的二級Cache，對於這類CPU來說，主板上提供的已是三級緩存了。
許多人認為，「緩存」是內存的一部分
許多技術文章都是這樣教授的
但是還是有很多人不知道緩存在什麼地方，緩存是做什麼用的
其實，緩存是CPU的一部分，它存在於CPU中
CPU存取數據的速度非常的快，一秒鍾能夠存取、處理十億條指令和數據（術語：CPU主頻1G），而內存就慢很多，快的內存能夠達到幾十兆就不錯了，可見兩者的速度差異是多麼的大
緩存是為了解決CPU速度和內存速度的速度差異問題
內存中被CPU訪問最頻繁的數據和指令被復制入CPU中的緩存，這樣CPU就可以不經常到象「蝸牛」一樣慢的內存中去取數據了，CPU只要到緩存中去取就行了，而緩存的速度要比內存快很多
這里要特別指出的是：
1.因為緩存只是內存中少部分數據的復製品，所以CPU到緩存中尋找數據時，也會出現找不到的情況（因為這些數據沒有從內存復制到緩存中去），這時CPU還是會到內存中去找數據，這樣系統的速度就慢下來了，不過CPU會把這些數據復制到緩存中去，以便下一次不要再到內存中去取。
2.因為隨著時間的變化，被訪問得最頻繁的數據不是一成不變的，也就是說，剛才還不頻繁的數據，此時已經需要被頻繁的訪問，剛才還是最頻繁的數據，現在又不頻繁了，所以說緩存中的數據要經常按照一定的演算法來更換，這樣才能保證緩存中的數據是被訪問最頻繁的
3.關於一級緩存和二級緩存
為了分清這兩個概念，我們先了解一下RAM
ram和ROM相對的，RAM是掉電以後，其中才信息就消失那一種，ROM在掉電以後信息也不會消失那一種
RAM又分兩種，
一種是靜態RAM，SRAM；一種是動態RAM，DRAM。前者的存儲速度要比後者快得多，我們現在使用的內存一般都是動態RAM。
有的菜鳥就說了，為了增加系統的速度，把緩存擴大不就行了嗎，擴大的越大，緩存的數據越多，系統不就越快了嗎
緩存通常都是靜態RAM，速度是非常的快，
但是靜態RAM集成度低（存儲相同的數據，靜態RAM的體積是動態RAM的6倍），
價格高（同容量的靜態RAM是動態RAM的四倍），
由此可見，擴大靜態RAM作為緩存是一個非常愚蠢的行為，
但是為了提高系統的性能和速度，我們必須要擴大緩存，
這樣就有了一個折中的方法，不擴大原來的靜態RAM緩存，而是增加一些高速動態RAM做為緩存，
這些高速動態RAM速度要比常規動態RAM快，但比原來的靜態RAM緩存慢，
我們把原來的靜態ram緩存叫一級緩存，而把後來增加的動態RAM叫二級緩存。
一級緩存和二級緩存中的內容都是內存中訪問頻率高的數據的復製品（映射），它們的存在都是為了減少高速CPU對慢速內存的訪問。
通常CPU找數據或指令的順序是：先到一級緩存中找，找不到再到二級緩存中找，如果還找不到就只有到內存中找了
二級緩存（L2 CACHE）是處理器內部的一些緩沖存儲器。它分內部和外部兩種晶元：內部的晶元二級緩存運行速度與主頻相同，而外部的二級緩存則只有主頻的一半。
由於一級緩存容量的限制，為了再次提高CPU的運算速度，在CPU外部放置一高速存儲器，即二級緩存。
二級緩存工作主頻比較靈活，可與CPU同頻，也可不同。CPU在讀取數據時，先在一級緩存中尋找，再從二級緩存尋找，然後是內存，在後是外存儲器。所以二級緩存對系統的影響是不容忽視的。
大量使用二級緩存帶來的結果是處理器運行效率的提升和成本價格的大幅度不等比提升。
舉例來說：伺服器上用的至強處理器和普通的P4處理器其內核基本上是一樣的，就是二級緩存不同。至強的二級緩存是2MB～16MB，P4的二級緩存是512KB，於是最便宜的至強也比最貴的P4貴，原因就在二級緩存不同。
㈢ Redis的LRU緩存淘汰演算法實現
LRU， 最近最少使用 （Least Recently Used，LRU），經典緩存演算法。
LRU會使用一個鏈表維護緩存中每個數據的訪問情況，並根據數據的實時訪問，調整數據在鏈表中的位置，然後通過數據在鏈表中的位置，表示數據是最近剛訪問的，還是已有段時間未訪問。
LRU會把鏈頭、尾分別設為MRU端和LRU端：
LRU可分成如下情況：
case2圖解：鏈表長度為5，從鏈表頭部到尾部保存的數據分別是5，33，9，10，8。假設數據9被訪問一次，則9就會被移動到鏈表頭部，同時，數據5和33都要向鏈表尾部移動一位。
所以若嚴格按LRU實現，假設Redis保存的數據較多，還要在代碼中實現：
最終導致降低Redis訪問性能。
所以，無論是為節省內存 or 保持Redis高性能，Redis並未嚴格按LRU基本原理實現，而是 提供了一個近似LRU演算法實現 。
Redis的內存淘汰機制是如何啟用近似LRU演算法的？redis.conf中的如下配置參數：
所以，一旦設定maxmemory選項，且將maxmemory-policy配為allkeys-lru或volatile-lru，近似LRU就被啟用。allkeys-lru和volatile-lru都會使用近似LRU淘汰數據，區別在於：
Redis如何實現近似LRU演算法的呢？
近似LRU演算法仍需區分不同數據的訪問時效性，即Redis需知道數據的最近一次訪問時間。因此，有了LRU時鍾：記錄數據每次訪問的時間戳。
Redis對每個KV對中的V，會使用個redisObject結構體保存指向V的指針。那redisObject除記錄值的指針，還會使用24 bits保存LRU時鍾信息，對應的是lru成員變數。這樣，每個KV對都會把它最近一次被訪問的時間戳，記錄在lru變數。
redisObject定義包含lru成員變數的定義：
每個KV對的LRU時鍾值是如何計算的？Redis Server使用一個實例級別的全局LRU時鍾，每個KV對的LRU time會根據全局LRU時鍾進行設置。
這全局LRU時鍾保存在Redis全局變數server的成員變數 lruclock
當Redis Server啟動後，調用initServerConfig初始化各項參數時，會調用getLRUClock設置lruclock的值：
於是，就得注意， 若一個數據前後兩次訪問的時間間隔 1s，那這兩次訪問的時間戳就是一樣的！ 因為LRU時鍾精度就是1s，它無法區分間隔小於1秒的不同時間戳！
getLRUClock函數將獲得的UNIX時間戳，除以LRU_CLOCK_RESOLUTION後，就得到了以LRU時鍾精度來計算的UNIX時間戳，也就是當前的LRU時鍾值。
getLRUClock會把LRU時鍾值和宏定義LRU_CLOCK_MAX（LRU時鍾能表示的最大值）做與運算。
所以默認情況下，全局LRU時鍾值是以1s為精度計算得UNIX時間戳，且是在initServerConfig中進行的初始化。
那Redis Server運行過程中，全局LRU時鍾值是如何更新的？和Redis Server在事件驅動框架中，定期運行的時間事件所對應的serverCron有關。
serverCron作為時間事件的回調函數，本身會周期性執行，其頻率值由redis.conf的 hz配置項 決定，默認值10，即serverCron函數會每100ms（1s/10 = 100ms）運行一次。serverCron中，全局LRU時鍾值就會按該函數執行頻率，定期調用getLRUClock進行更新：
這樣，每個KV對就能從全局LRU時鍾獲取最新訪問時間戳。
對於每個KV對，它對應的redisObject.lru在哪些函數進行初始化和更新的呢？
對於一個KV對，其LRU時鍾值最初是在這KV對被創建時，進行初始化設置的，這初始化操作在 createObject函數 中調用，當Redis要創建一個KV對，就會調用該函數。
createObject除了會給redisObject分配內存空間，還會根據maxmemory_policy配置，初始化設置redisObject.lru。
LRU_CLOCK返回當前全局LRU時鍾值。因為一個KV對一旦被創建，就相當於有了次訪問，其對應LRU時鍾值就表示了它的訪問時間戳：
那一個KV對的LRU時鍾值又是何時再被更新？
只要一個KV對被訪問，其LRU時鍾值就會被更新！而當一個KV對被訪問時，訪問操作最終都會調用 lookupKey 。
lookupKey會從全局哈希表中查找要訪問的KV對。若該KV對存在，則lookupKey會根據maxmemory_policy的配置值，來更新鍵值對的LRU時鍾值，也就是它的訪問時間戳。
而當maxmemory_policy沒有配置為LFU策略時，lookupKey函數就會調用LRU_CLOCK函數，來獲取當前的全局LRU時鍾值，並將其賦值給鍵值對的redisObject結構體中的lru變數
這樣，每個KV對一旦被訪問，就能獲得最新的訪問時間戳。但你可能好奇：這些訪問時間戳最終是如何被用於近似LRU演算法進行數據淘汰的？
Redis之所以實現近似LRU，是為減少內存資源和操作時間上的開銷。
近似LRU主要邏輯在performEvictions。
performEvictions被evictionTimeProc調用，而evictionTimeProc函數又是被processCommand調用。
processCommand，Redis處理每個命令時都會調用：
然後，isSafeToPerformEvictions還會再次根據如下條件判斷是否繼續執行performEvictions：
一旦performEvictions被調用，且maxmemory-policy被設置為allkeys-lru或volatile-lru，近似LRU就被觸發執行了。
執行可分成如下步驟：
調用getMaxmemoryState評估當前內存使用情況，判斷當前Redis Server使用內存容量是否超過maxmemory配置值。
若未超過maxmemory ，則返回C_OK，performEvictions也會直接返回。
getMaxmemoryState評估當前內存使用情況的時候，若發現已用內存超出maxmemory，會計算需釋放的內存量。這個釋放內存大小=已使用內存量-maxmemory。
但已使用內存量並不包括用於主從復制的復制緩沖區大小，這是getMaxmemoryState通過調用freeMemoryGetNotCountedMemory計算的。
而若當前Server使用的內存量超出maxmemory上限 ，則performEvictions會執行while循環淘汰數據釋放內存。
為淘汰數據，Redis定義數組EvictionPoolLRU，保存待淘汰的候選KV對，元素類型是evictionPoolEntry結構體，保存了待淘汰KV對的空閑時間idle、對應K等信息：
這樣，Redis Server在執行initSever進行初始化時，會調用evictionPoolAlloc為EvictionPoolLRU數組分配內存空間，該數組大小由EVPOOL_SIZE決定，默認可保存16個待淘汰的候選KV對。
performEvictions在淘汰數據的循環流程中，就會更新這個待淘汰的候選KV對集合，即EvictionPoolLRU數組。
performEvictions調用evictionPoolPopulate，其會先調用dictGetSomeKeys，從待采樣哈希表隨機獲取一定數量K：
於是，dictGetSomeKeys返回採樣的KV對集合。evictionPoolPopulate根據實際采樣到的KV對數量count，執行循環：調用estimateObjectIdleTime計算在采樣集合中的每一個KV對的空閑時間：
接著，evictionPoolPopulate遍歷待淘汰的候選KV對集合，即EvictionPoolLRU數組，嘗試把采樣的每個KV對插入EvictionPoolLRU數組，取決於如下條件之一：
有一成立，evictionPoolPopulate就能把采樣KV對插入EvictionPoolLRU數組。等所有采樣鍵值對都處理完後，evictionPoolPopulate函數就完成對待淘汰候選鍵值對集合的更新了。
接下來，performEvictions開始選擇最終被淘汰的KV對。
因evictionPoolPopulate已更新EvictionPoolLRU數組，且該數組里的K，是按空閑時間從小到大排好序了。所以，performEvictions遍歷一次EvictionPoolLRU數組，從數組的最後一個K開始選擇，若選到的K非空，就把它作為最終淘汰的K。
該過程執行邏輯：
一旦選到被淘汰的K，performEvictions就會根據Redis server的惰性刪除配置，執行同步刪除或非同步刪除：
至此，performEvictions就淘汰了一個K。若此時釋放的內存空間還不夠，即沒有達到待釋放空間，則performEvictions還會 重復執行 前面所說的更新待淘汰候選KV對集合、選擇最終淘汰K的過程，直到滿足待釋放空間的大小要求。
performEvictions流程：
近似LRU演算法並未使用耗時且耗空間的鏈表，而使用 固定大小的待淘汰數據集合 ，每次隨機選擇一些K加入待淘汰數據集合。
最後，按待淘汰集合中K的空閑時間長度，刪除空閑時間最長的K。
根據LRU演算法的基本原理，發現若嚴格按基本原理實現LRU演算法，則開發的系統就需要額外內存空間保存LRU鏈表，系統運行時也會受到LRU鏈表操作的開銷影響。
而Redis的內存資源和性能都很重要，所以Redis實現近似LRU演算法：
一個演算法的基本原理和演算法的實際執行，在系統開發中會有一定折中，需綜合考慮所開發的系統，在資源和性能方面的要求，以避免嚴格按照演算法實現帶來的資源和性能開銷。
㈣ 常用緩存替換演算法的理解
目前已知的常用緩存替換演算法有：隨機法、先入先出法FIFO、 最近最少使用法LRU 、最不經常使用法LFU等。緩存替換演算法有很多種，FIFO是最簡單的，LRU是最常用的，最優緩存替換演算法則是命中率最佳的。因為我們無法預知數據的未來訪問模式，通常最優替換演算法是無法實現的。
LRU是最常用的緩存替換演算法，當前的很多論文，甚至頂會論文都是基於LRU演算法進行緩存替換演算法的改進。作為最通用的替換策略，LRU演算法適合具有良好時間局部性的負載，能較好的適應程序負載的動態變化。LRU演算法利用歷史信息預測數據的使用情況，將最久沒有使用的塊替換，良好的反映程序的局部性。
㈤ LRU 緩存淘汰演算法
當要緩存某個數據的時候，先在鏈表中查找這個數據。如果沒有找到，則直接將數據放到鏈表的尾部；如果找到了，我們就把它移動到鏈表的尾部，然後淘汰頭部數據。
因為查找數據需要遍歷鏈表，所以單純用鏈表實現的 LRU 緩存淘汰演算法的時間復雜很高，是 O(n)。如果我們將散列表和雙向鏈表兩種數據結構組合使用，可以將這三個操作的時間復雜度都降低到 O(1)。
因為我們的散列表是通過鏈表法解決散列沖突的，所以每個結點會在兩條鏈中。一個鏈是剛剛我們提到的雙向鏈表，另一個鏈是散列表中的拉鏈。前驅和後繼指針是為了將結點串在雙向鏈表中，hnext 指針是為了將結點串在散列表的拉鏈中。
這整個過程涉及的查找操作都可以通過散列表來完成。其他的操作，比如刪除頭結點、鏈表尾部插入數據等，通過雙向鏈表都可以在 O(1) 的時間復雜度內完成。所以，這三個操作的時間復雜度都是 O(1)。
至此，我們就通過散列表和雙向鏈表的組合使用，實現了一個高效的、支持 LRU 緩存淘汰演算法的緩存系統原型。
散列表中數據是經過散列函數打亂之後無規律存儲的，但是 LinkedHashMap可以 做到按照數據的插入順序來存儲。
每次調用 put() 函數，往 LinkedHashMap 中添加數據的時候，都會將數據添加到鏈表的尾部，再次將鍵值為 3 的數據放入到 LinkedHashMap 的時候，會先查找這個鍵值是否已經有了，然後，再將已經存在的 (3,11) 刪除，並且將新的 (3,26) 放到鏈表的尾部，訪問到 key 為 5 的數據的時候，我們將被訪問到的數據移動到鏈表的尾部。
所以按照訪問時間排序的 LinkedHashMap 本身就是一個支持 LRU 緩存淘汰策略的緩存系統。
散列表這種數據結構雖然支持非常高效的數據插入、刪除、查找操作，但是散列表中的數據都是通過散列函數打亂之後無規律存儲的。也就說，它無法支持按照某種順序快速地遍歷數據。如果希望按照順序遍歷散列表中的數據，那我們需要將散列表中的數據拷貝到數組中，然後排序，再遍歷。
因為散列表是動態數據結構，不停地有數據的插入、刪除，所以每當我們希望按順序遍歷散列表中的數據的時候，都需要先排序，那效率勢必會很低。為了解決這個問題，我們將散列表和鏈表（或者跳錶）結合在一起使用。
㈥ 什麼叫緩存
所謂的緩存，就是將程序或系統經常要調用的對象存在內存中，一遍其使用時可以快速調用，不必再去創建新的重復的實例。這樣做可以減少系統開銷，提高系統效率。
1、通過文件緩存；顧名思義文件緩存是指把數據存儲在磁碟上，不管你是以XML格式，序列化文件DAT格式還是其它文件格式；
2、內存緩存；也就是創建一個靜態內存區域，將數據存儲進去，例如我們B/S架構的將數據存儲在Application中或者存儲在一個靜態Map中。
3、本地內存緩存；就是把數據緩存在本機的內存中。
4、分布式緩存機制；可能存在跨進程，跨域訪問緩存數據
對於分布式的緩存，此時因為緩存的數據是放在緩存伺服器中的，或者說，此時應用程序需要跨進程的去訪問分布式緩存伺服器。
(6)時間緩存演算法擴展閱讀
當我們在應用中使用跨進程的緩存機制，例如分布式緩存memcached或者微軟的AppFabric，此時數據被緩存在應用程序之外的進程中。
每次，當我們要把一些數據緩存起來的時候，緩存的API就會把數據首先序列化為位元組的形式，然後把這些位元組發送給緩存伺服器去保存。
同理，當我們在應用中要再次使用緩存的數據的時候，緩存伺服器就會將緩存的位元組發送給應用程序，而緩存的客戶端類庫接受到這些位元組之後就要進行反序列化的操作了，將之轉換為我們需要的數據對象。
㈦ 緩存替換演算法是什麼
Cache替換演算法是影響代理緩存系統性能的一個重要因素，一個好的Cache替換演算法可以產生較高的命中率。目前已經提出的演算法可以劃分為以下三類： （1）傳統替換演算法及其直接演化，其代表演算法有：①LRU（Least Recently Used）演算法：將最近最少使用的內容替換出Cache；②LFU（Lease Frequently Used）演算法：將訪問次數最少的內容替換出Cache；③Pitkow/Recker[10]提出了一種替換演算法：如果Cache中所有內容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU演算法進行替換。 （2）基於緩存內容關鍵特徵的替換演算法，其代表演算法有：①Size[10]替換演算法：將最大的內容替換出Cache；②LRU— MIN[11]替換演算法：該演算法力圖使被替換的文檔個數最少。設待緩存文檔的大小為S，對Cache中緩存的大小至少是S的文檔，根據LRU演算法進行替換；如果沒有大小至少為S的對象，則從大小至少為S/2的文檔中按照LRU演算法進行替換；③LRU—Threshold[11] 替換演算法：和LRU演算法一致，只是大小超過一定閾值的文檔不能被緩存 ...
㈧ LFU緩存策略演算法實現
LFU（Least Frequently Used），最近最少使用策略，也就是說在一段時間內，數據被使用頻次最少的，優先被淘汰。
它是一種用於管理計算機內存的緩存演算法，採用LFU演算法的最簡單方法是為每個載入到緩存的塊分配一個計數器。每次引用該塊時，計數器將增加一。當緩存達到容量並有一個新的內存塊等待插入時，系統將搜索計數器最低的塊並將其從緩存中刪除。
我們可以在鏈表的開始插入元素，然後每插入一次計數一次，接著按照次數重新排序鏈表，如果次數相同的話，按照插入時間排序，然後從鏈表尾部選擇淘汰的數據，這是一個最簡單的LFU實現的思路。
這里實現了comparable介面，覆寫了compare方法，這里 的主要作用就是在排序的時候需要用到，在compare方法裡面我們首先比較節點的訪問次數，在訪問次數相同的情況下比較節點的訪問時間，這里是為了 在排序方法裡面通過比較key來選擇淘汰的key。
這里採用linkedHashMap的主要原因是維護key的順序。
添加元素的邏輯主要是先從緩存中根據key獲取節點，如果獲取不到，證明是新添加的元素，然後和容量比較，大於預定容量的話，需要找出count計數最小(計數相同的情況下，選擇時間最久)的節點，然後移除掉那個。
我們知道內存淘汰演算法，常見的除了LFU還有LRU,LRU和LFU側重點不同，LRU主要體現在對元素的使用時間上，而LFU主要體現在對元素的使用頻次上。
LFU的缺陷是：在短期的時間內，對某些緩存的訪問頻次很高，這些緩存會立刻晉升為熱點數據，而保證不會淘汰，這樣會駐留在系統內存裡面。而實際上，這部分數據只是短暫的高頻率訪問，之後將會長期不訪問，瞬時的高頻訪問將會造成這部分數據的引用頻率加快，而一些新加入的緩存很容易被快速刪除，因為它們的引用頻率很低。
我們要根據業務場景選擇合適的內存淘汰策略。
參考資料： https://mp.weixin.qq.com/s/qq3sieAkfvUpOS48Mwlczw