LRU(Least Recently Use)算法，是用來判斷一批數(shù)據(jù)中，最近最少使用算法。它底層數(shù)據(jù)結(jié)構(gòu)由Hash和鏈表結(jié)合實(shí)現(xiàn)，使用Hash是為了保障查詢效率為O(1)，使用鏈表保障刪除元素效率為O(1)。

LRU算法是用來判斷最近最少使用到元素，常被用在緩存中數(shù)據(jù)清理、內(nèi)存淘汰相關(guān)的場景，它底層是由Hash表和雙向鏈表構(gòu)成，Hash主要用來存儲(chǔ)key和指向鏈表節(jié)點(diǎn)的指針，雙向鏈表就是用來實(shí)現(xiàn)最近最少使用算法的數(shù)據(jù)結(jié)構(gòu)，新訪問的元素會(huì)加入到頭部或者尾部（就看最終從哪個(gè)反向取了，我們這里定為頭部），如果是已經(jīng)訪問的元素，并不會(huì)新添加到鏈表中，而是將鏈表中原來存在的這個(gè)節(jié)點(diǎn)移動(dòng)到頭部，最終鏈表中越靠近尾部的元素，代表最近最少使用的元素。

為什么要額外組合使用Hash和鏈表？單個(gè)數(shù)據(jù)結(jié)構(gòu)也能完成不是嗎？

為了提交效能，Hash的優(yōu)勢是查找元素為O(1)，但是移動(dòng)元素是O(n)，鏈表查找元素復(fù)雜度是O(n)，但是移動(dòng)元素復(fù)雜度是O(1)，所以為了提高效率，結(jié)構(gòu)兩種數(shù)據(jù)結(jié)構(gòu)各自的優(yōu)勢，利用Hash的O(1)，來查找元素是否存在，利用鏈表的O(1)來移動(dòng)元素位置。

Redis近似LRU算法

什么是Redis近似LRU算法，為什么Redis不直接使用LRU算法？

近似LRU算法是Redis采用LRU算法思想，實(shí)現(xiàn)一個(gè)近似LRU的算法，在原LRU算法中需要維護(hù)一個(gè)Hash和鏈表，而Redis本身可以理解為一個(gè)大的字典，那就需要額外的去維護(hù)一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)，Redis本身就是要經(jīng)受大量數(shù)據(jù)的沖擊的，所以這個(gè)鏈表將會(huì)占用更大的內(nèi)存。Redis的宗旨就是高效，所以它沒有使用這樣的一個(gè)鏈表。它的做法如下：

Redis最開始的做法：
1、當(dāng)設(shè)置了LRU回收策略之后，對(duì)元素進(jìn)行訪問時(shí)，會(huì)調(diào)用一次server.lruclock方法，獲取Redis時(shí)鐘時(shí)間戳（redis時(shí)鐘默認(rèn)1毫秒更新一次）并進(jìn)行取模（防止時(shí)間戳遞增，最后超過了24bit），記錄在元素value中l(wèi)ru屬性中。
2、當(dāng)內(nèi)存達(dá)到maxmemory時(shí)，會(huì)隨機(jī)抽取5（可以通過maxmemory-policy設(shè)定）個(gè)樣本key進(jìn)行時(shí)間戳判斷，淘汰時(shí)間戳最小的（也就是最久遠(yuǎn)的一個(gè)key）

優(yōu)點(diǎn)：不用額外的維護(hù)一個(gè)鏈表，節(jié)省了內(nèi)存，同時(shí)隨機(jī)采樣淘汰方式也避免了大數(shù)據(jù)量key遍歷處理的耗時(shí)。

缺點(diǎn)：因?yàn)槭请S機(jī)采樣刪除，所以會(huì)出現(xiàn)更早key遲遲沒有被采樣刪除的情況。釘子戶。

Redis3.0 做了LRU算法升級(jí)

Redis在3.0之后對(duì)LRU算法做了升級(jí)，加入了候選池Pool(16字節(jié))，首次抽樣5個(gè)會(huì)放入都Pool中，并按照時(shí)間大小lru排序，后續(xù)每次選取的Key的lru必須要小于pool的最小值（也就是key要比pool中的更早），才放入pool中，直到pool滿，當(dāng)有新元素加入時(shí)，只需要將pool中最萬的key（也就是最大的）刪除即可。

升級(jí)之后的算法，可以更大密度的將更久沒有使用的key刪除，減少了釘子戶的存在。

RedisLFU算法

在Redis4.0 推出了LFU算法，這個(gè)是基于訪問次數(shù)維護(hù)的回收算法，算法和LRU差不多，就是在lru中加入了請求次數(shù)的計(jì)數(shù)count維護(hù)。從時(shí)間和頻次兩個(gè)維度來計(jì)算key的熱度。他的好處是，如果一個(gè)key很就沒有被訪問到，突然最近被訪問了一次，在LRU算法中，它是不容易被淘汰的，但是在LRF算法中，會(huì)統(tǒng)計(jì)它訪問頻次，發(fā)現(xiàn)不足定位很熱的key，所以還是會(huì)被刪除。所以LFU算法很適合用于熱點(diǎn)數(shù)據(jù)的刪除策略。