实现一个LRU Cache

算法/数据结构

1.什么是Cache和LRU Cache

狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

CPU中Cache能极大提高存取数据和指令的时间，让整个存储器(Cache和内存)既有Cache的高速度，又能有内存的大容量；操作系统中的内存Page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存，从而提高访问速度；数据库中数据查询也用到Cache来提高效率；即便是Powerbuilder的DataWindow数据处理也用到了Cache的类似设计。

Cache的算法设计常见的有FIFO(first in first out)和LRU(least recently used)。LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

注：

动态随机存取存储器（Dynamic Random Access Memory，DRAM）是一种半导体存储器，主要的作用原理是利用电容内存储电荷的多寡来代表一个二进制比特（bit）是1还是0。由于在现实中电容会有漏电的现象，导致电位差不足而使记忆消失，因此除非电容经常周期性地充电，否则无法确保记忆长存。由于这种需要定时刷新的特性，因此被称为“动态”存储器。相对来说，“静态”存储器（SRAM）只要存入数据后，纵使不刷新也不会丢失记忆。

静态随机存取存储器（Static Random-Access Memory, SRAM）是随机存取存储器的一种。所谓的“静态”，是指这种存储器只要保持通电，里面储存的数据就可以恒常保持[1]。相对之下，动态随机存取内存（DRAM）里面所储存的数据就需要周期性地更新。然而，当电力供应停止时，SRAM储存的数据还是会消失（被称为volatile memory），这与在断电后还能储存资料的ROM或闪存是不同的。

下图是存储器层次结构，以前在《深入理解计算机系统》这本书看到的，顺便放到此处：

2.数据结构

Cache中的存储空间往往是有限的，当Cache中的存储块被用完，而需要把新的数据载入到Cache的时候，就需要设计一种良好的算法来完成数据块的替换。LRU的思想是基于“最近用到的数据被重用的概率比较早用到的大的多”这个设计规则来实现的。

为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满时，淘汰链表最后的位置就是了。

注：
对于双向链表的使用，基于两个考虑。首先是Cache中块的命中可能是随机的，和载入进来的顺序无关。其次，双向链表插入、删除很快，可以灵活的调整相互间的次序，时间复杂度为O(1)。

我们要访问某个结点，就需要顺序地一个个找，时间复杂度是 O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点，或者返回未找到。

所以：LRU的典型实现是双向链表和哈希表，双向链表用于存储数据结点，并且它是按照结点最近被使用的时间来存储的。哈希表用于快速访问某个结点。

3.一个面试题

Question: Implement LRU cache algorithm 
Implement the LRU cache algorithm with the following interface: 
—————————————————————————————————
T get(K key);
void put(K key, T data);

此题参考价值还是蛮大的，不少公司，特别后台开发职位会考到此题。hawstein大牛用C++代码实现了，我们看下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// A simple LRU cache written in C++
// Hash map + doubly linked list
#include <iostream>
#include <vector>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

template &lt;class K, class T&gt;
struct Node{
 K key;
 T data;
 Node *prev, *next;
};

template &lt;class K, class T&gt;
class LRUCache{
public:
 LRUCache(size_t size){
 entries_ = new Node&lt;K,T&gt;[size];
 for(int i=0; i< size; ++i)// 存储可用结点的地址
 free_entries_.push_back(entries_+i);
 head_ = new Node<K,T>;
 tail_ = new Node<K,T>;
 head_->prev = NULL;
 head_->next = tail_;
 tail_->prev = head_;
 tail_->next = NULL;
 }
 ~LRUCache(){
 delete head_;
 delete tail_;
 delete[] entries_;
 }
 void Put(K key, T data){
 Node<K,T> *node = hashmap_[key];
 if(node){ // node exists
 detach(node);
 node->data = data;
 attach(node);
 }
 else{
 if(free_entries_.empty()){// 可用结点为空，即cache已满
 node = tail_->prev;
 detach(node);
 hashmap_.erase(node->key);
 }
 else{
 node = free_entries_.back();
 free_entries_.pop_back();
 }
 node->key = key;
 node->data = data;
 hashmap_[key] = node;
 attach(node);
 }
 }
 T Get(K key){
 Node<K,T> *node = hashmap_[key];
 if(node){
 detach(node);
 attach(node);
 return node->data;
 }
 else{// 如果cache中没有，返回T的默认值。与hashmap行为一致
 return T();
 }
 }
private:
 // 分离结点
 void detach(Node<K,T>* node){
 node->prev->next = node->next;
 node->next->prev = node->prev;
 }
 // 将结点插入头部
 void attach(Node<K,T>* node){
 node->prev = head_;
 node->next = head_->next;
 head_->next = node;
 node->next->prev = node;
 }
private:
 hash_map<K, Node<K,T>* > hashmap_;
 vector<Node<K,T>* > free_entries_; // 存储可用结点的地址
 Node<K,T> *head_, *tail_;
 Node<K,T> *entries_; // 双向链表中的结点
};

int main(){
 hash_map<int, int> map;
 map[9]= 999;
 cout<<map[9]<<endl;
 cout<<map[10]<<endl;
 LRUCache<int, string> lru_cache(100);
 lru_cache.Put(1, "one");
 cout<<lru_cache.Get(1)<<endl;
 if(lru_cache.Get(2) == "")
 lru_cache.Put(2, "two");
 cout<<lru_cache.Get(2);
 return 0;
}

看到此处，我就想研究下redis和memcache的cache是怎么设计的了。等下次研究完后，再做下笔记吧。

参考链接：

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

http://hawstein.com/posts/lru-cache-impl.html

http://blog.csdn.net/hexinuaa/article/details/6630384