分類導(dǎo)航

常見緩存算法和LRU的c++實(shí)現(xiàn)

發(fā)布時(shí)間：2017年01月16日作者：文章轉(zhuǎn)自網(wǎng)絡(luò)，版權(quán)歸原作者所有，反饋可立刻刪除 (該文來自筆記，點(diǎn)擊查看原文)

對于web開發(fā)而言，緩存必不可少，也是提高性能最常用的方式。無論是瀏覽器緩存(如果是chrome瀏覽器，可以通過chrome:://cache查看)，還是服務(wù)端的緩存(通過memcached或者redis等內(nèi)存數(shù)據(jù)庫)。緩存不僅可以加速用戶的訪問，同時(shí)也可以降低服務(wù)器的負(fù)載和壓力。那么，了解常見的緩存淘汰算法的策略和原理就顯得特別重要。

常見的緩存算法

LRU (Least recently used) 最近最少使用，如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高。
LFU (Least frequently used) 最不經(jīng)常使用，如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來一段時(shí)間內(nèi)被使用的可能性也很小。
FIFO (Fist in first out) 先進(jìn)先出，如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個(gè)算法，LRU算法會將近期最不會訪問的數(shù)據(jù)淘汰掉。LRU如此流行的原因是實(shí)現(xiàn)比較簡單，而且對于實(shí)際問題也很實(shí)用，良好的運(yùn)行時(shí)性能，命中率較高。下面談?wù)勅绾螌?shí)現(xiàn)LRU緩存：

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營銷培訓(xùn)

新數(shù)據(jù)插入到鏈表頭部
每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部
當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

LRU Cache具備的操作：

set(key,value)：如果key在hashmap中存在，則先重置對應(yīng)的value值，然后獲取對應(yīng)的節(jié)點(diǎn)cur，將cur節(jié)點(diǎn)從鏈表刪除，并移動到鏈表的頭部；若果key在hashmap不存在，則新建一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)放到鏈表的頭部。當(dāng)Cache存滿的時(shí)候，將鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。
get(key)：如果key在hashmap中存在，則把對應(yīng)的節(jié)點(diǎn)放到鏈表頭部，并返回對應(yīng)的value值；如果不存在，則返回-1。

LRU的c++實(shí)現(xiàn)

LRU實(shí)現(xiàn)采用雙向鏈表 + Map 來進(jìn)行實(shí)現(xiàn)。這里采用雙向鏈表的原因是：如果采用普通的單鏈表，則刪除節(jié)點(diǎn)的時(shí)候需要從表頭開始遍歷查找，效率為O(n)，采用雙向鏈表可以直接改變節(jié)點(diǎn)的前驅(qū)的指針指向進(jìn)行刪除達(dá)到O(1)的效率。使用Map來保存節(jié)點(diǎn)的key、value值便于能在O(logN)的時(shí)間查找元素,對應(yīng)get操作。

雙鏈表節(jié)點(diǎn)的定義：

struct CacheNode {  int key;      // 鍵
  int value;    // 值
  CacheNode *pre, *next;  // 節(jié)點(diǎn)的前驅(qū)、后繼指針
  CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

分類導(dǎo)航

常見緩存算法和LRU的c++實(shí)現(xiàn)

常見的緩存算法

LRU緩存

LRU的c++實(shí)現(xiàn)

延伸閱讀

我想了解如何學(xué)習(xí)