前言

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

常見的緩存算法

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

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個算法，LRU算法會將近期最不會訪問的數據淘汰掉。LRU如此流行的原因是實現比較簡單，而且對于實際問題也很實用，良好的運行時性能，命中率較高。下面談談如何實現LRU緩存：

1. 新數據插入到鏈表頭部
2. 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部
3. 當鏈表滿的時候，將鏈表尾部的數據丟棄

LRU Cache具備的操作：

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

LRU的c++實現

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

雙鏈表節點的定義：

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

對于LRUCache這個類而言，構造函數需要指定容量大小

LRUCache(int capacity){ size = capacity;  // 容量 head = NULL;   // 鏈表頭指針 tail = NULL;   // 鏈表尾指針}

雙鏈表的節點刪除操作：

void remove(CacheNode *node){ if (node -> pre != NULL) { node -> pre -> next = node -> next; } else { head = node -> next; } if (node -> next != NULL) { node -> next -> pre = node -> pre; } else { tail = node -> pre; }}

將節點插入到頭部的操作：

void setHead(CacheNode *node){ node -> next = head; node -> pre = NULL; if (head != NULL) { head -> pre = node; } head = node; if (tail == NULL) { tail = head; }}

get(key)操作的實現比較簡單，直接通過判斷Map是否含有key值即可，如果查找到key，則返回對應的value，否則返回-1;

int get(int key){ map<int, CacheNode *>::iterator it = mp.find(key); if (it != mp.end()) { CacheNode *node = it -> second; remove(node); setHead(node); return node -> value; } else { return -1; }}

set(key, value)操作需要分情況判斷。如果當前的key值對應的節點已經存在，則將這個節點取出來，并且刪除節點所處的原有的位置，并在頭部插入該節點；如果節點不存在節點中，這個時候需要在鏈表的頭部插入新節點，插入新節點可能導致容量溢出，如果出現溢出的情況，則需要刪除鏈表尾部的節點。

void set(int key, int value){ map<int, CacheNode *>::iterator it = mp.find(key); if (it != mp.end()) { CacheNode *node = it -> second; node -> value = value; remove(node); setHead(node); } else { CacheNode *newNode = new CacheNode(key, value); if (mp.size() >= size) {  map<int, CacheNode *>::iterator iter = mp.find(tail -> key);  remove(tail);  mp.erase(iter); } setHead(newNode); mp[key] = newNode; }}

總結

好了，至此，LRU算法的實現操作就完成了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。