redis之數(shù)據(jù)過期清除策略、緩存淘汰策略詳解

更新時間：2025年04月23日 11:13:18 作者：fixAllenSun

這篇文章主要介紹了redis之數(shù)據(jù)過期清除策略、緩存淘汰策略的用法,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

過期策略

Redis 所有的數(shù)據(jù)結(jié)構(gòu)都可以設(shè)置過期時間，時間一到，就會自動刪除?？梢韵胂罄锩嬗幸粋€專門刪除過期數(shù)據(jù)的線程，數(shù)據(jù)已過期就立馬刪除。

這個時候可以思考一下，會不會因為同一時間太多的 key 過期，以至于線程忙不過來。同時因為 Redis 是單線程的，刪除的時間也會占用線程的處理時間，如果刪除的太過于繁忙，會不會導致線上讀寫指令出現(xiàn)卡頓。

立即刪除

它會在設(shè)置鍵的過期時間的同時，創(chuàng)建一個定時器，當鍵到了過期時間，定時器會立即對鍵進行刪除。
這個策略能夠保證過期鍵的盡快刪除，快速釋放內(nèi)存空間。

優(yōu)點：

立即刪除能保證內(nèi)存中數(shù)據(jù)的最大新鮮度，因為它保證過期鍵值會在過期后馬上被刪除，其所占用的內(nèi)存也會隨之釋放。
對內(nèi)存來說是非常友好的。

缺點：

立即刪除對cpu是最不友好的。
因為刪除操作會占用cpu的時間，如果剛好碰上了cpu很忙的時候，比如正在做交集或排序等計算的時候，就會給cpu造成額外的壓力。

總結(jié)：

立即刪除對cpu不友好，但是對內(nèi)存友好，實際性質(zhì)就是用處理器性能換區(qū)內(nèi)存空間。

惰性刪除（被動過期）

數(shù)據(jù)到達過期時間，不做處理。等下次訪問該數(shù)據(jù)時，如果未過期，返回數(shù)據(jù) ；發(fā)現(xiàn)已過期，刪除，返回不存在。
開啟惰性刪除：lazyfree-lazy-eviction=yes

優(yōu)點：

對于cpu來說是非常友好的，減少了cpu資源的占有。

缺點：

如果一個鍵已經(jīng)過期，而這個鍵又仍然保留在redis中，那么只要這個過期鍵不被刪除，它所占用的內(nèi)存就不會釋放。因此對于內(nèi)存是很不友好的。
在使用惰性刪除策略時，如果數(shù)據(jù)庫中有非常多的過期鍵，而這些過期鍵又恰好沒有被訪問到的話，那么它們也許永遠也不會被刪除(除非用戶手動執(zhí)行FLUSHDB)，我們甚至可以將這種情況看作是一種內(nèi)存泄漏–無用的垃圾數(shù)據(jù)占用了大量的內(nèi)存，而服務(wù)器卻不會自己去釋放它們，這對于運行狀態(tài)非常依賴于內(nèi)存的Redis服務(wù)器來說,肯定不是一個好消息

定期刪除

定期刪除策略是前兩種策略的折中：
定期刪除策略每隔一段時間執(zhí)行一次刪除過期鍵操作并通過限制刪除操作執(zhí)行時長和頻率來減少刪除操作對CPU時間的影響。

過期key的集合

redis 會將每個設(shè)置了過期時間的 key 放入到一個獨立的字典中，以后會定時遍歷這個字典來刪除到期的 key。除了定時遍歷之外，它還會使用惰性策略來刪除過期的 key。定期刪除是集中處理，惰性刪除是零散處理。

定時掃描策略

Redis 默認會每秒進行十次過期掃描，過期掃描不會遍歷過期字典中所有的 key，而是采用了一種簡單的貪心策略。

從過期字典中隨機 20 個 key；
刪除這 20 個 key 中已經(jīng)過期的 key；
如果過期的 key 比率超過 1/4，那就重復步驟 1；

于此同時為了保證過期掃描不會出現(xiàn)循環(huán)過度，導致線程卡死現(xiàn)象，算法還增加了掃描時間的上限，默認不會超過 25ms。

（1）定時過期到底是怎么實現(xiàn)？

定期去循環(huán)找過期的key，然后去刪掉！

（2）去循環(huán)誰？是不是所有的key？

并不是去循環(huán)所有的key，因為Redis里經(jīng)常會存放巨多的數(shù)據(jù)，對我們需要經(jīng)常清理，全部遍歷一遍顯然不現(xiàn)實，而Redis采取的是取樣這個操作。

1-不是一次性把所有設(shè)置了過期時間的數(shù)據(jù)拿出來，而是按hash桶維度取里面取值，取到20個值為止，如果第一個有30個，那么也會取30個！如果一直取不到20，那么最多400個桶
2-刪除取出值的過期key
3-如果400個桶都取不到值，或者取出的key 刪除的比例大于10%,繼續(xù)上面的操作
4-每循環(huán)16次會去檢測時間，超過指定時間就跳出

ps:按hash桶維度取key的邏輯是：最后一個桶會取完桶內(nèi)所有的key，不論里面有多少個，每取完一個桶判斷一下是否取到了20個，最多取400個桶。

（3）多久循環(huán)一次？

redis里面有個很重要的概念叫做時間事件，那么這個時間事件是什么意思了，就是定時去做一些事情，那么redis里面有個方法叫serverCron()，在文件server.c中；就是它的時間事件去調(diào)用的清理
它里面干了很多事情，比如：

1-更新服務(wù)器的各類統(tǒng)計信息，比如時間、內(nèi)存占用、數(shù)據(jù)庫占用情況等
2-清理數(shù)據(jù)庫中的過期鍵值對。
3-關(guān)閉和清理連接失效的客戶端
4-嘗試進行持久化操作

那么這個時間事件多久去執(zhí)行一次呢，其實是由你們自己決定的！

redis.conf 中通過 hz 配置，hz代表的意思是每秒執(zhí)行多少次！默認10次，也就是100ms我們就會去執(zhí)行定期過期?。?/p>

特別注意的情況

設(shè)想一個大型的 Redis 實例中所有的 key 在同一時間過期了。Redis 會持續(xù)掃描過期字典 (循環(huán)多次)，直到過期字典中過期的 key 變得稀疏，才會停止 (循環(huán)次數(shù)明顯下降)。這就會導致線上讀寫請求出現(xiàn)明顯的卡頓現(xiàn)象。導致這種卡頓的另外一種原因是內(nèi)存管理器需要頻繁回收內(nèi)存頁，這也會產(chǎn)生一定的 CPU 消耗。

即使算法還增加了掃描時間的上限，也是會出現(xiàn)卡頓現(xiàn)象。假如有 101 個客戶端同時將請求發(fā)過來了，然后前 100 個請求的執(zhí)行時間都是 25ms，那么第 101 個指令需要等待多久才能執(zhí)行？2500ms，這個就是客戶端的卡頓時間，是由服務(wù)器不間斷的小卡頓積少成多導致的（假如每次都達到了掃描上線25ms）。

所以開發(fā)的時候就需要特別注意，避免大量key在同一時間過期?？梢越okey在固定的過期時間上+隨機范圍的時間

定期刪除注意事項

如果刪除操作執(zhí)行次數(shù)過多、執(zhí)行時間太長，就會導致和定時刪除同樣的問題：占用大量cpu資源去進行刪除操作

如果刪除操作次數(shù)太少、執(zhí)行時間短，就會導致和惰性刪除同樣的問題：內(nèi)存資源被持續(xù)占用，得不到釋放。

所以定時刪除最關(guān)鍵的就在于執(zhí)行時長和頻率的設(shè)置，可在redis的配置文件中配置

對于hz參數(shù)，官方不建議超過100，否則會把cpu造成比較大的壓力

緩存淘汰策略

緩存淘汰策略的作用

（1）當 Redis 內(nèi)存超出物理內(nèi)存限制時，內(nèi)存的數(shù)據(jù)會開始和磁盤產(chǎn)生頻繁的交換，交換會讓 Redis 的性能急劇下降，對于訪問量比較頻繁的 Redis 來說，這樣龜速的存取效率基本上等于不可用。

（2）一般生產(chǎn)上的redis內(nèi)存都會設(shè)置一個內(nèi)存上限（maxmemory），如果有許多沒有加過期時間的數(shù)據(jù)，長期下來就會把redis內(nèi)存打滿，出現(xiàn)OOM異常。

（3）定期刪除是使用簡單的貪心算法，會出現(xiàn)一些沒有被抽查到的數(shù)據(jù)，而惰性刪除也會出現(xiàn)一些長時間沒有訪問得數(shù)據(jù)，這就會導致大量過期的key堆積在內(nèi)存中，導致redis內(nèi)存空間緊張或者很快耗盡。所以必須要有一個兜底方案。這個方案就是緩存淘汰策略。

八種緩存淘汰策略

noeviction：不會繼續(xù)服務(wù)寫請求 (DEL 請求可以繼續(xù)服務(wù))，讀請求可以繼續(xù)進行。這樣可以保證不會丟失數(shù)據(jù)，但是會讓線上的業(yè)務(wù)不能持續(xù)進行。這是默認的淘汰策略。
volatile-lru：嘗試淘汰設(shè)置了過期時間的 key，最少使用的 key 優(yōu)先被淘汰。沒有設(shè)置過期時間的 key：不會被淘汰，這樣可以保證需要持久化的數(shù)據(jù)不會突然丟失。
allkeys-lru：區(qū)別于 volatile-lru，這個策略要淘汰的 key 對象是全體的 key 集合，而不只是過期的 key 集合。這意味著沒有設(shè)置過期時間的 key 也會被淘汰。
volatile-ttl：跟上面一樣，除了淘汰的策略不是 LRU，而是 key 的剩余壽命 ttl 的值，ttl 越小越優(yōu)先被淘汰。
volatile-random：對所有設(shè)置了過期時間的key隨機淘汰。
allkeys-random：對所有key隨機淘汰
volatile-lfu：對設(shè)置了過期時間的key使用lfu算法進行刪除
allkeys-lfu：對所有key使用lfu算法進行刪除

總結(jié)：

volatile-xxx：策略只會針對帶過期時間的 key 進行淘汰，allkeys-xxx 策略會對所有的 key 進行淘汰。
如果你只是拿 Redis 做緩存，那應該使用 allkeys-xxx，客戶端寫緩存時不必攜帶過期時間。
如果你還想同時使用 Redis 的持久化功能，那就使用 volatile-xxx 策略，這樣可以保留沒有設(shè)置過期時間的 key，它們是永久的 key 不會被 LRU 算法淘汰。

PS：是在config文件中配置的策略：

#maxmemory-policy noeviction

默認就是不淘汰，如果滿了，能讀不能寫！

LRU和LFU

LRU（Least Recently Used：最久未使用）

根據(jù)時間軸來走，很久沒用的數(shù)據(jù)只要最近有用過，我就默認是有效的。也就是說這個策略的意思是先淘汰長時間沒用過的，那么怎么去判斷一個redis數(shù)據(jù)有多久沒訪問了，Redis是這樣做的：

redis的所有數(shù)據(jù)結(jié)構(gòu)的對外對象里，它里面有個字段叫做lru

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
 /* 
\*LRU time (relative to global lru_clock) or
\* LFU data (least significant 8 bits frequency
\* and most significant 16 bits access time). 
*/
int refcount;
void *ptr;
} robj;

每個對象都有1個LRU的字段，看它的說明，好像LRU跟我們后面講的LFU都跟這個字段有關(guān)，并且這個lru代表的是一個時間相關(guān)的內(nèi)容。

那么我們大概能猜出來，redis去實現(xiàn)lru肯定跟我們這個對象的lru相關(guān)?。?/p>

首先，我告訴大家，這個lru在LRU算法的時候代表的是這個數(shù)據(jù)的訪問時間的秒單位??！但是只有24bit，無符號位，所以這個lru記錄的是它訪問時候的秒單位時間的后24bit！

用Java來寫就是：

long timeMillis=System.currentTimeMillis();
System.out.println(timeMillis/1000); //獲取當前秒
System.out.println(timeMillis/1000 & ((1<<24)-1));//獲取秒的后24位

是獲取當前時間的最后24位，那么當我們最后的24bit都是1了的時候，時間繼續(xù)往前走，那么我們獲取到的時間是不是就是24個0了！

舉個例子：

11111111111111111000000000011111110 假如這個是我當前秒單位的時間，獲取后8位 是 11111110
11111111111111111000000000011111111 獲取后8位 是11111111
11111111111111111000000000100000000 獲取后8位 是00000000

所以，它有個輪詢的概念，它如果超過24位，又會從0開始！所以我們不能直接的用系統(tǒng)時間秒單位的24bit位去減對象的lru,而是要判斷一下，還有一點，為了性能，我們系統(tǒng)的時間不是實時獲取的，而是用redis的時間事件來獲取，所以，我們這個時間獲取是100ms去獲取一次。

現(xiàn)在我們知道了原來redis對象里面原來有個字段是記錄它訪問時間的，那么接下來肯定有個東西去跟這個時間去比較，拿到差值！

我們?nèi)タ聪略创aevict.c文件

unsigned long long estimateObjectIdleTime(robj *o) {
	//獲取秒單位時間的最后24位
	unsigned long long lruclock = LRU_CLOCK();
	//因為只有24位，所有最大的值為2的24次方-1
	//超過最大值從0開始，所以需要判斷l(xiāng)ruclock（當前系統(tǒng)時間）跟緩存對象的lru字段的大小
	if (lruclock >= o->lru) {
	//如果lruclock>=robj.lru，返回lruclock-o->lru，再轉(zhuǎn)換單位
	return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
	} else {
	//否則采用lruclock + (LRU_CLOCK_MAX - o->lru)，得到對象的值越小，返回的值越大，越大越容易被淘汰
	return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
	LRU_CLOCK_RESOLUTION;
	}
}

我們發(fā)現(xiàn)，跟對象的lru比較的時間也是serverCron下面的當前時間的秒單位的后面24位！但是它有個判斷，有種情況是系統(tǒng)時間跟對象的LRU的大小，因為最大只有24位，會超過?。?/p>

所以，我們可以總結(jié)下我們的結(jié)論：

Redis數(shù)據(jù)對象的LRU用的是server.lruclock這個值，server.lruclock又是每隔100ms生成的系統(tǒng)時間的秒單位的后24位！所以server.lruclock可以理解為延遲了100ms的當前時間秒單位的后24位！

用server.lruclock 與對象的lru字段進行比較，因為server.lruclock只獲取了當前秒單位時間的后24位，所以肯定有個輪詢。所以，我們會判斷server.lruclock跟對象的lru字段進行比較，如 server.lruclock>obj.lru，那么我們用server.lruclock-obj.lru,否則server.lruclock+(LRU_CLOCK_MAX-obj.lru),得到lru越小，那么返回的數(shù)據(jù)越大，相差越大的就會被淘汰！

LFU（Least Frequently Used：最不常用）

但是LFU的有個致命的缺點！就是它只會加不會減！為什么說這是個缺點

舉個例子：去年有一個熱搜，今年有一個熱搜，熱度相當，但是去年的那個因為有時間的積累，所以點擊次數(shù)高，今年的點擊次數(shù)因為剛發(fā)生，所以累積起來的次數(shù)沒有去年的高，那么我們?nèi)绻腰c擊次數(shù)作為衡量，是不是應該刪除的就是今年的？這就導致了新的進不來舊的出不去

所以我們來看redis它是怎么實現(xiàn)的！怎么解決這個缺點！

我們還是來看我們的redisObject

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
 /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;

我們看它的lru，它如果被用作LFU的時候！它前面16位代表的是時間，后8位代表的是一個數(shù)值，frequency是頻率，應該就是代表這個對象的訪問次數(shù)，我們先給它叫做counter。

那么這個16位的時間跟8位的counter到底有啥用呢？8位我們還能猜測下，可能就是這個對象的訪問次數(shù)！

我們淘汰的時候，是不是就是去根據(jù)這個對象使用的次數(shù)，按照小的就去給它淘汰掉。

其實，差不多就是這么個意思。

還有個問題，如果8位用作訪問次數(shù)的話，那么8位最大也就2的8次方，就是255次，夠么？如果，按照我們的想法，肯定不夠，那么redis去怎么解決呢？

既然不夠，那么讓它不用每次都加就可以了,能不能讓它值越大，我們加的越慢就能解決這個問題

redis還加了個東西，讓你們自己能主宰它加的速率，這個東西就是lfu-log-factor！它配置的越大，那么對象的訪問次數(shù)就會加的越慢。

源碼：

uint8_t LFULogIncr(uint8_t counter) {
	//如果已經(jīng)到最大值255，返回255 ，8位的最大值
	if (counter == 255) return 255;
	//得到隨機數(shù)（0-1）
	double r = (double)rand()/RAND_MAX;
	//LFU_INIT_VAL表示基數(shù)值（在server.h配置）
	double baseval = counter - LFU_INIT_VAL;
	//如果達不到基數(shù)值，表示快不行了，baseval =0
	if (baseval < 0) baseval = 0;
	//如果快不行了，肯定給他加counter
	//不然，按照幾率是否加counter，同時跟baseval與lfu_log_factor相關(guān)
	//都是在分子，所以2個值越大，加counter幾率越小
	double p = 1.0/(baseval*server.lfu_log_factor+1);
	if (r < p) counter++;
	return counter;
}

所以，LFU加的邏輯我們可以總結(jié)下：

（1）如果已經(jīng)是最大值，我們不再加！因為到達255的幾率不是很高！可以支撐很大很大的數(shù)據(jù)量！

（2）counter屬于隨機添加，添加的幾率根據(jù)已有的counter值和配置lfu-log-factor相關(guān)，counter值越大，添加的幾率越小，lfu-log-factor配置的值越大，添加的幾率越?。?/p>

我們的這個16bit記錄的是這個對象的訪問時間的分單位的后16位，每次訪問或者操作的時候，都會去跟當前時間的分單位的后16位去比較，得到多少分鐘沒有訪問了！然后去減去對應的次數(shù)！

那么這個次數(shù)每分鐘沒訪問減多少了，就是根據(jù)我們的配置lfu-decay-time。

這樣就能夠?qū)崿F(xiàn)我們的LFU，并且還解決了LFU不能減的問題。

總結(jié)如圖：

貼出減的源碼：

unsigned long LFUDecrAndReturn(robj *o) {
	//lru字段右移8位，得到前面16位的時間
	unsigned long ldt = o->lru >> 8;
	//lru字段與255進行&運算（255代表8位的最大值），
	//得到8位counter值
	unsigned long counter = o->lru & 255;
	//如果配置了lfu_decay_time，用LFUTimeElapsed(ldt) 除以配置的值
	//LFUTimeElapsed(ldt)源碼見下
	//總的沒訪問的分鐘時間/配置值，得到每分鐘沒訪問衰減多少
	unsigned long num_periods = server.lfu_decay_time ?LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
	if (num_periods)
	//不能減少為負數(shù)，非負數(shù)用couter值減去衰減值
	counter = (num_periods > counter) ? 0 : counter - num_periods;
	return counter;
}

LFUTimeElapsed方法源碼(evict.c)：

//對象ldt時間的值越小，則說明時間過得越久
unsigned long LFUTimeElapsed(unsigned long ldt) {
	//得到當前時間分鐘數(shù)的后面16位
	unsigned long now = LFUGetTimeInMinutes();
	//如果當前時間分鐘數(shù)的后面16位大于緩存對象的16位
	//得到2個的差值
	if (now >= ldt) return now-ldt;
	//如果緩存對象的時間值大于當前時間后16位值，則用65535-ldt+now得到差值
	return 65535-ldt+now;
}

所以，LFU減邏輯我們可以總結(jié)下：

（1）我們可以根據(jù)對象的LRU字段的前16位得到對象的訪問時間（分鐘），根據(jù)跟系統(tǒng)時間比較獲取到多久沒有訪問過！

（2）根據(jù)lfu-decay-time（配置），代表每分鐘沒訪問減少多少counter，不能減成負數(shù)

區(qū)別

LRU：最近最少使用頁面置換算法，淘汰最長時間未被使用的頁面，看頁面最后一次被使用到發(fā)生調(diào)度的時間長短，首先淘汰最長時間未被使用的頁面。
LFU：最近最不常用頁面置換算法，淘汰一定時期內(nèi)被訪問次數(shù)最少的頁，看一定時間段內(nèi)頁面被使用的頻率，淘汰一定時期內(nèi)被訪問次數(shù)最少的頁

舉個栗子：

某次時期Time為10分鐘，如果每分鐘進行一次調(diào)頁,主存塊為3,若所需頁面走向為2 1 2 1 2 3 4
假設(shè)到頁面4時會發(fā)生缺頁中斷
若按LRU算法,應換頁面1(1頁面最久未被使用)，但按LFU算法應換頁面3(十分鐘內(nèi),頁面3只使用了一次)
可見LRU關(guān)鍵是看頁面最后一次被使用到發(fā)生調(diào)度的時間長短,而LFU關(guān)鍵是看一定時間段內(nèi)頁面被使用的頻率!

手寫LRU算法

底層shuju

使用LinkedHashMap實現(xiàn)

/**
 * @Description :
 * @Author : huangcong
 * @Date : 2023/6/28 9:48
 **/
public class LinkedHashMapLru<K, V> extends LinkedHashMap<K, V> {

    private Integer initialCapacity;

    public LinkedHashMapLru(Integer initialCapacity) {
        super(initialCapacity, 0.75F, Boolean.FALSE);
        this.initialCapacity = initialCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > initialCapacity;
    }

    public Object getValue(Object key) {
        Object v = super.get(key);
        if (Objects.isNull(v)) {
            return -1;
        }
        return v;
    }

    public static void main(String[] args) {
        LinkedHashMapLru<Object, Object> hashMapLru = new LinkedHashMapLru<>(3);
        hashMapLru.put(1, "a");
        hashMapLru.put(2, "b");
        hashMapLru.put(3, "c");
        System.out.println(hashMapLru.entrySet());

        // key存在變更其數(shù)據(jù)
        hashMapLru.put(3, "l");
        System.out.println(hashMapLru.entrySet());

        // 當緩存容量達到上限時，它應該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值
        hashMapLru.put(4, "d");
        System.out.println(hashMapLru.entrySet());

        hashMapLru.put(5, "f");
        System.out.println(hashMapLru.entrySet());

        // 獲取數(shù)據(jù) get(key) - 如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1
        Object value =hashMapLru.getValue(1);
        System.out.println(value);
    }
}

其他方式實現(xiàn)

/**
 * @Description : 構(gòu)造一個node節(jié)點，承載數(shù)據(jù)
 * @Author : hc
 * @Date : 2023/6/28 12:14
 **/
public class Node<K, V> {

    K key;

    V value;

    Node<K, V> pre;

    Node<K, V> next;

    public Node() {
    }

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.pre = this.next = null;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

/**
 * @Description :雙向鏈表
 * @Author : hc
 * @Date : 2023/6/28 12:23
 **/
public class LruCache <K,V>{

    Node<K,V> head;
    Node<K,V> tail;

    public LruCache() {
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.pre = head;
    }

    // 頭插法，靠近頭部的是最新的數(shù)據(jù)
    public void add(Node<K,V> node){
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    public void delete(Node<K,V> node){
        node.next.pre =node.pre;
        node.pre.next = node.next;
        node.next = null;
        node.pre = null;
    }

    public Node getNode(){
        return tail.pre;
    }

    // 打印鏈表
    public String getCache(){
        StringBuffer stringBuffer = new StringBuffer();
        Node<K, V> node = head.next;
        while (node != tail){
            stringBuffer.append(node.key+"="+node.value + "\r\n");
            node = node.next;
        }
        return stringBuffer.toString();
    }
}

/**
 * @Description :
 * hash表：通過hash函數(shù)計算出hash值，然后（hash值 % 數(shù)組大?。┑玫綄獢?shù)組中的位置
 * @Author : hc
 * @Date : 2023/6/28 16:23
 **/
public class Lru {

    private Integer cacheSize; // 規(guī)定容器大小
    private Map<Integer,Node<Integer,Integer>> map; // hash表，方便查找
    private LruCache<Integer,Integer> doubleLinkedMap;// 雙向鏈表，方便插入以及刪除

    public Lru(Integer cacheSize) {
    this.cacheSize = cacheSize;
    map = new HashMap<>();
    doubleLinkedMap = new LruCache<>();
    }

    public int get(Integer key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedMap.delete(node);
        doubleLinkedMap.add(node);
        return node.value;
    }

    public Integer put(Integer key,Integer value){
        // 如果哈希表中有，替換節(jié)點的value值
        if (map.containsKey(key)){
            Node<Integer, Integer> node = map.get(key);
            node.setValue(value);
            doubleLinkedMap.delete(node);
            doubleLinkedMap.add(node);
            return key;
        }
        Node<Integer, Integer> node = new Node<>(key, value);
        // 如果hash沒有，且容器中數(shù)據(jù)已經(jīng)達到了規(guī)定大小，刪除最后一個數(shù)據(jù)，在頭部添加一個最新數(shù)據(jù)
        if (map.size() >= cacheSize){
            Node lastNode = doubleLinkedMap.getNode();
            doubleLinkedMap.delete(lastNode);
            doubleLinkedMap.add(node);
            map.remove(key);
            map.put(key,node);
            return key;
        }
        // 如果hash沒有，且容器中數(shù)據(jù)未達到了規(guī)定大小，直接在頭部添加一個最新數(shù)據(jù)
        doubleLinkedMap.add(node);
        map.put(key,node);
        return key;
    }

    // 刪除節(jié)點
    public Integer delete(Integer key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedMap.delete(node);
        map.remove(key);
        return key;
    }

    public static void main(String[] args) {
        Lru lru = new Lru(3);
        lru.put(1,1);
        lru.put(2,2);
        lru.put(3,3);
        System.out.println(lru.doubleLinkedMap.getCache());

        lru.put(2,4);
        System.out.println(lru.doubleLinkedMap.getCache());

        lru.put(4,4);
        System.out.println(lru.doubleLinkedMap.getCache());

        int i = lru.get(3);
        System.out.println(i);
        System.out.println(lru.doubleLinkedMap.getCache());
    }
}

運行結(jié)果：

3=3
2=2
1=1

2=4
3=3
1=1

4=4
2=4
3=3

3
3=3
4=4
2=4

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章:

亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

redis之數(shù)據(jù)過期清除策略、緩存淘汰策略詳解

目錄

過期策略

立即刪除

惰性刪除（被動過期）

定期刪除

過期key的集合

定時掃描策略

特別注意的情況

定期刪除注意事項

緩存淘汰策略

緩存淘汰策略的作用

八種緩存淘汰策略

LRU和LFU

LRU（Least Recently Used：最久未使用）

LFU（Least Frequently Used：最不常用）

區(qū)別

手寫LRU算法

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

redis之數(shù)據(jù)過期清除策略、緩存淘汰策略詳解

目錄

過期策略

立即刪除

惰性刪除（被動過期）

定期刪除

過期key的集合

定時掃描策略

特別注意的情況

定期刪除注意事項

緩存淘汰策略

緩存淘汰策略的作用

八種緩存淘汰策略

LRU和LFU

LRU（Least Recently Used：最久未使用）

LFU（Least Frequently Used：最不常用）

區(qū)別

手寫LRU算法

總結(jié)

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

redis之數(shù)據(jù)過期清除策略、緩存淘汰策略詳解