C++实现最基本的LRUCache服务器缓存

目录：

一、介绍；

二、数据结构；

三、主要的两个函数接口Put()和Get()；

四、C++代码实现；

后台开发必备知识，不过我不是搞这个的，只是因为很久以前就想写这些东西，事情多，拖到现在。写的过程里面发现很多问题，不会全部说，最后会顺带提一提。

注意，本篇笔记只是对接口写法做了记录，并没有进行更严格的设计和限制，包括更严密的封装，这里只是学习它实现的原理。

不过有些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完成了调试和测试，下面先给出代码：

  1 #include <iostream>
  2 #include<ext/hash_map>
  3 #include<vector>
  4 #include<assert.h>
  5 #include<string>
  6 #include<stdlib.h>
  7 #include<stdio.h>
  8 #include<iomanip>
  9 using namespace std;
 10 //grep -R "hash_map" /usr/include . Find the file and you will know what the namespace is.
 11 using namespace __gnu_cxx;
 12 
 13 
 14 template<class K, class T>
 15 struct Node
 16 {
 17     K key;
 18     T data;
 19     Node *next;
 20     Node *prev;
 21 };
 22 
 23 template<class K,class T>
 24 class LRUCache
 25 {
 26 public:
 27     LRUCache(size_t size)         //typedef unsigned int size_t
 28     {
 29         entries = new Node<K,T>[size];
 30         assert(entries!=NULL);
 31         for(int i = 0; i < size; i++)
 32         {
 33             linkedList.push_back(entries+i);      //Store the addr.
 34         }
 35         //Initial the double linklist
 36         head = new Node<K,T>;
 37         tail = new Node<K,T>;
 38         head->prev = NULL;
 39         head->next = tail;
 40         tail->next = NULL;
 41         tail->prev = head;
 42     }
 43     ~LRUCache()
 44     {
 45         delete head;
 46         delete tail;
 47         delete []entries;
 48     }
 49     void Put(K key,T data)
 50     {
 51         Node<K,T> *node = hashmap[key];
 52         if(node == NULL)  //node == NULL means it doesn't exist
 53         {
 54             if(linkedList.empty())  //linkedList is empty means all avaliable space have been allocated
 55             {
 56                 node = tail->prev;    //Detach the last code
 57                 Detach(node);
 58                 hashmap.erase(node->key);
 59             }
 60             else
 61             {
 62                 node = linkedList.back();  //Allocate an addr to the node
 63                 linkedList.pop_back();     //Pop the addr mentioned above
 64             }
 65             node->key = key;
 66             node->data = data;
 67             hashmap[key] = node;
 68             Attach(node);
 69         }
 70         else
 71         {
 72             Detach(node);
 73             node->data = data;
 74             Attach(node);
 75         }
 76     }
 77 
 78     T Get(K key)
 79     {
 80         Node<K,T> * node = hashmap[key];
 81         if(node)
 82         {
 83             Detach(node);
 84             Attach(node);      //Attach the node to the fisrt place
 85             return node->data;
 86         }
 87         else
 88         {
 89             return T();
 90             /*U can write some codes to test it:
 91              *void main()
 92              *{
 93              *char c = int();
 94               cout<<c<<endl;
 95               int i = char();
 96               cout<<i<<endl;
 97               cout<<char()<<endl;
 98               cout<<int()<<endl;
 99               }*/
100         }
101     }
102 private:
103     void Attach(Node<K,T>* node)
104     {
105         assert(node != NULL);
106         node->next = head->next;
107         node->next->prev = node;
108         node->prev = head;
109         head->next = node;
110     }
111     void Detach(Node<K,T>* node)
112     {
113         assert(node != NULL);
114         node->prev->next = node->next;
115         node->next->prev = node->prev;
116     }
117 
118 private:
119     hash_map<K,Node<K,T>*> hashmap;
120     vector<Node<K,T>*> linkedList;
121     Node<K,T>* head;
122     Node<K,T>* tail;
123     Node<K,T>* entries; //temp nodes
124 
125 };
126 
127 
128 int main()
129 {
130     cout << "Hello World!" << endl;
131     LRUCache<int,string> cache(10);
132     /*
133     string str = "test";
134     char buffer[10];
135     int i = 1;
136     //itoa(1,c,10);   //Not existing in the ANSI-C or C++.
137     sprintf(buffer,"%d",i);   //The alternative to the code above.
138     str.append(buffer);
139     cout<<str<<endl;
140     */
141     cache.Put(1,"test1");
142     cout<<cache.Get(1)<<endl;
143     if(cache.Get(2)=="")
144     {
145         cout<<"Node doesn't exist!"<<endl;
146     }
147     cache.Put(0,"test0");
148     cache.Put(3,"test3");
149     cache.Put(1,"test_1_again");
150     cache.Put(12,"test12");
151     cache.Put(56,"test56");
152     cout<<cache.Get(3)<<endl;
153     /*Error code. And I don't know why!!!!
154         string str="test";
155         char buffer[10];
156         for(int i = 0 ; i < 14; i++)
157         {
158             if(sprintf(buffer,"%d",i)<10)
159             {
160                 str.append(buffer);
161                 cache.Put(i,str);
162                 str="test";
163             }
164         }
165         for(int i =0; i < 14; i++)
166         {
167             if(!(i/5))
168             {
169                 cout<<cache.Get(i)<<setw(4);
170             }
171             cout<<endl;
172         }*/
173     return 0;
174 }

LRUCache

调试的时候我发现了一个问题：

坑爹了，全部节点的next指针全部都指向自己，这样的话链表长得像什么样子呢？应该是这样：

这个错误到底是怎么来的？

我反复地看代码，节点的链入（Attach）和取出（Detach）都是没有问题的，而且，插入新节点的时候，已经插入过的节点为什么没有了？Attach方法既然是正确的，那为什么节点的next为什么会指向自己？

综合上面两个问题，我突然意识到：那只能是分配地址的时候出现问题了！
所以回到构造函数分配地址的部分，我发现在for循环里面，本应是：
linkedList.push_back(entries+i);
这样就能顺序存储分配好的地址。
但我竟然把i写成了1，所以每个地址都成了同一个！吐血的经历。

最后代码更正之后即可正确运行：

对应的测试代码为：

最后一笔带过编写过程中遇到的三个主要问题：

1、make install 源码包安装的软件怎么卸载（最好用--prefix=""指定安装路径，这样你卸载的时候直接卸载那个安装路径的文件夹）;
2、QtCreator调试的时候为什么不显示变量（因为你用的python版本是3.0以上的，Qt的gdb调试器不支持，自己重新装一个2.X版本的，参考链接：http://blog.hostilefork.com/qtcreator-debugger-no-locals-ubuntu/）；
3、测试代码的时候出现一点小错误，搞了很久但还是不知道为什么（在main函数中注释的最后一段代码，有兴趣的可以自己调试一下）。

参考文章：

1、http://www.cs.uml.edu/~jlu1/doc/codes/lruCache.html

2、http://blog.csdn.net/xiaofei_hah0000/article/details/8993617