後台開發必備知識，不過我不是搞這個的，只是因為很久以前就想寫這些東西，事情多，拖到現在。寫的過程裡面發現很多問題，不會全部說，最後會順帶提一提。 注意，本篇筆記只是對接口寫法做了記錄，並沒有進行更嚴格的設計和限制，包括更嚴密的封裝，這裡只是學習它實現的原理。 不過有些idea還是要知道的，系統定時對緩存進行清除並加入滿足條件的新數據，是根據：訪問時間，訪問次數，可用緩存容量（分配到的內存）等因素決定的，實際設計其實很多東西需要考慮。 一、介紹： LRU，Least Recently Used，最近最少使用，服務器緩存常用算法的一種。 比如說一些系統登錄的操作，不可能每次你訪問系統都去調用數據庫的東西，如果能劃出一些空間來，比如說500M，用來緩存這些東西，這樣用戶訪問的時候先在緩存裡找，找不到，再去訪問數據庫，同時把被訪問的內容放到緩存裡面（我們可以假設這些東西還會經常被訪問）。然而，我們分配用來做緩存（Cache）的空間肯定是有限的，總不可能從數據庫讀的東西全部放到緩存裡，所以，當緩存裡的內容達到上限值的時候，我們就要把最少使用的東西寫回數據庫，再將新的訪問內容從數據庫暫存到緩存裡面。 二、數據結構： 最常用的數據結構實現方式是hash_map和Double-Linked List，hash_map只是為了實現鍵值key-value對應，這樣就避免了每次尋找特定值都要在雙線鏈表裡面順序查找，服務器是沒辦法負擔這種低效率的查找方法的。 我們可以為鏈表節點寫一個結構體，用來定義節點的類型；然後專門寫一個類用來組織緩存信息的存放——以雙鏈表的形式。 復制代碼 template<class K, class T> struct Node { K key; T data; Node *next; Node *prev; }; 復制代碼 復制代碼 template<class K,class T> class LRUCache { public: LRUCache(size_t size); //typedef unsigned int size_t ～LRUCache(); void Put(K key,T data); T Get(K key); private: void Attach(Node<K,T>* node); void Detach(Node<K,T>* node); private: hash_map<K,Node<K,T>*> hashmap; vector<Node<K,T>*> linkedList; Node<K,T>* head; Node<K,T>* tail; Node<K,T>* entries; //temp nodes }; 復制代碼 看代碼太枯燥，我畫了個UML圖： 三、主要的兩個函數接口Put()和Get()： 最基本的，不是存，就是取。那修改呢？合並到存裡面去了，通過鍵值key查找一個hash_map對應的value，如果value不是NULL，那麼更新value的內容即可。其實服務器緩存比較多作的是讀多寫少的東西。 因為代碼實在是太枯燥了，所以針對Put函數和Get函數畫了兩張流程圖： 其中，Detach(node)表示將這個節點從雙鏈表中解出，成為一個獨立的節點；Attach(node)表示將node插入到頭節點head後面（表示它可能再次被用到），這樣的話，如果自己再設計一個GetFirst()函數，就能直接獲取上次的訪問結果，這種訪問連hash_map都不需要用到。 流程講解： 在上述Put函數流程圖中，注意第一個判斷“node==NULL”，這個node地址是通過hashmap映射而來的：1、如果不是NULL，說明這個節點已經存在，那麼將該節點的數據data重寫以後加到鏈表頭； 2、如果是NULL，還要進行第二個判斷“分配地址的linkedList是不是已經空了”： 2.1、如果空了，說明全部可用地址已經分配完了，那麼，將原鏈表的最後一個節點踢出鏈表（應寫入數據庫），然後將被踢出點的hashmap中對應的key-value擦除，然後再加入新節點，並在hashmap中對應好新節點的key-value； 2.2、如果不空，那麼從linkedList中分配個新地址給這個節點，同時linkedList要彈出分配完的地址，然後再將新節點加入鏈表中，對應好hashmap中的key-value。 要注意，hashmap用來對應key-value，這裡是方便查找；而vector變量linkedList也只是在初始化的時候存儲了一塊連續地址，用來分配地址，它們兩者都不是用來直接構建鏈表的，鏈表是你自己建立的。 Get()函數就比較簡單了： 四、C++代碼實現： 代碼不是我原創的（後面給出原文地址），不過理清思路之後我自己實現了一遍，測試的過程實在是各種奇葩和辛苦（因為一個不注意的小地方）。 代碼實現裡用到了hash_map，注意，這個不是C++標准的一部分，所以你要自己去庫文件裡找找，一般來說庫文件都是在/usr/include下面的了，cd到這個文件夾，然後用grep找一下： cd /usr/include grep -R "hash_map" 最後你會發現是這個頭文件：<ext/hash_map>，用文本文檔打開來看一下，因為是限制了命名空間的，會發現有兩個可用的命名空間，其中一個是__gnu_cxx。 代碼我一開始是用Qt寫的，不過後來發現Qt沒法調試（後面再說），於是最後使用Eclipse完成了調試和測試，下面先給出代碼： LRUCache 調試的時候我發現了一個問題： 坑爹了，全部節點的next指針全部都指向自己，這樣的話鏈表長得像什麼樣子呢？應該是這樣： 這個錯誤到底是怎麼來的？ 我反復地看代碼，節點的鏈入（Attach）和取出（Detach）都是沒有問題的，而且，插入新節點的時候，已經插入過的節點為什麼沒有了？Attach方法既然是正確的，那為什麼節點的next為什麼會指向自己？ 綜合上面兩個問題，我突然意識到：那只能是分配地址的時候出現問題了！ 所以回到構造函數分配地址的部分，我發現在for循環裡面，本應是： linkedList.push_back(entries+i); 這樣就能順序存儲分配好的地址。 但我竟然把i寫成了1，所以每個地址都成了同一個！吐血的經歷。
