簡單的LRU Cache設計與實現
來自： http://www.cnblogs.com/zengzy/p/5167827.html
get(key)：若緩存中存在key，返回對應的value，否則返回-1
set(key,value):若緩存中存在key，替換其value，否則插入key及其value，如果插入時緩存已經滿了，應該使用LRU算法把最近最久沒有使用的key踢出緩存。
設計1：
cache使用數組，每個key再關聯一個時間戳，時間戳可以直接用個long long類型表示，在cache中維護一個最大的時間戳：
- get的時候把key的時間戳變為最大時間戳+1
- set的時候， 數據從前往后存儲
如果key存在，更新key的時間戳為當前cache中最大的時間戳+1，并更新value；
如果key不存在，
若緩存滿，在整個緩存中查找時間戳最小的key，其存儲位置作為新key的存儲位置，設置key的時間戳為最大時間戳+1
若緩存未滿，設置key的時間戳為最大時間戳+1，存儲位置為第一個空閑位置
分析下時間空間復雜度，get的時候，需要從前往后找key，時間為O(N)，set的時候，也要從前往后找key，當緩存滿的時候，還得找到時間戳最小的key，時間復雜度為O(N)。除了緩存本身，并沒有使用其他空間，空間復雜度為O(1)。 這個速度顯然是比較慢的，隨著數據量的增大，get和set速度越來越慢。可能有人會想到用哈希表作為底層存儲，這樣get的時間復雜度確實可以減低為O(1)，set的時候，只要緩存沒有滿，也可以在O(1)的時間完，但在緩存滿的時候，依然需要每次遍歷找時間戳最小的key，時間復雜度還是O(N)。
設計2：
cache底層使用單鏈表，同時用一個哈希表存儲每個key對應的鏈表結點的前驅結點，并記錄鏈表尾結點的key
- get時，從哈希表中找到key對應的鏈表結點，挪到鏈表頭，更新指向尾結點的key
- set時，如果key存在，那么找到鏈表結點，并挪到鏈表頭，更新指向尾結點的key
如果key不存在，
若緩存滿，重用鏈表尾結點，設置新key和value，并挪到鏈表頭，更新指向尾結點的key
若緩存未滿，直接插入結點到鏈表頭，若是第一結點，更新指向尾結點的key
get,set時間復雜度O(1)，總的空間復雜度O(N)。比前面的設計好一點。下面的再來看下關于設計2的兩個實現
實現1，自定義鏈表
為了方便鏈表的插入與刪除，使用了帶頭結點head的鏈表，所以真正有效的第一個結點是head->next。另外，只是簡單的實現，沒有容錯，不支持并發，簡單的內存管理
ps. 用雙向鏈表來實現會簡單寫，這里用單鏈表和哈希表共同實現了雙向鏈表的功效，也就是哈希除了用來查找，還指示了key對應的結點的前驅結點。
struct Node{
int _key;
int _value;
Node _next;
Node(int key,int value,Node next):_key(key),_value(value),_next(next){}
};
class LRUCache{
public:
LRUCache(int capacity) {
_capacity = capacity;
_size = 0;
_last = 0;
_cur_begin = _begin = (char ) malloc(sizeof(Node)(capacity+1));
_head = new (_cur_begin) Node(0,0,NULL);//在指定內存上構造對象
_cur_begin += sizeof(Node);
}
~LRUCache(){
if(_begin!=NULL){
while(_cur_begin > _begin){
_cur_begin -= sizeof(Node);
((Node*)_cur_begin)->~Node();//先釋放內存上的對象
}
free(_begin);//再釋放內存
}
}
int get(int key) {
int value = -1;//初始時假設key對應的結點不存在
Node* pre_node_of_key = umap_prenodes[key];//key對應的結點的前驅結點
if(pre_node_of_key !=NULL){//key結點存在
Node* node = pre_node_of_key->_next;//key對應的結點
pre_node_of_key->_next = node->_next;
if(pre_node_of_key->_next!=NULL){
umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;
}
node->_next = _head->_next;
if(node->_next!=NULL){//node有后繼，更新后繼的前驅結點
umap_prenodes[node->_next->_key] = node;
}
_head->_next = node;
umap_prenodes[key] = _head;
/*更新_last*/
if(_last == key ){
_last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key );
}
value = node->_value;
}
return value;
}
void set(int key, int value) {
Node* node = NULL;
Node* pre_node_of_key = umap_prenodes[key];//key對應的結點的前驅結點
if(pre_node_of_key != NULL){//key對應的結點存在，孤立key對應的結點，也就是從鏈表中把結點取出來，重新鏈接鏈表
node = pre_node_of_key->_next;//key對應的結點
pre_node_of_key->_next = node->_next;
if(pre_node_of_key->_next!=NULL){
umap_prenodes[pre_node_of_key->_next->_key] = pre_node_of_key;//更新前驅
}
node->_value = value; //重置結點值
/*更新_last*/
if(_last == key ){
_last = ( pre_node_of_key == _head ? key : pre_node_of_key->_key );
}
}else{//結點不存在
if(_capacity == 0){//緩沖區為空
return ;
}
if(_size == _capacity){//緩存滿，重用最后一個結點
Node* pre_node_of_last = umap_prenodes[_last];//最后一個結點的前驅結點
umap_prenodes[pre_node_of_last->_next->_key] = NULL;
node = new (pre_node_of_last->_next) Node(key,value,NULL);//重用最后一個結點
pre_node_of_last->_next = NULL;//移出最后一個結點
_last = ( pre_node_of_last == _head ? key : pre_node_of_last->_key ); //更新指向最后一個結點的key
}else{//緩沖未滿，使用新結點
node = new (_cur_begin) Node(key,value,NULL);
_cur_begin += sizeof(Node);
_size++;
if(_size==1){
_last = key;
}
}
}
/*把node插入到第一個結點的位置*/
node->_next = _head->_next;
if(node->_next!=NULL){//node有后繼，更新后繼的前驅結點
umap_prenodes[node->_next->_key] = node;
}
_head->_next = node;
umap_prenodes[key] = _head;
}
private:
int _size;
int _capacity;
int _last;//_last是鏈表中最后一個結點的key
Node _head;
unordered_map<int,Node> umap_prenodes;//存儲key對應的結點的前驅結點，鏈表中第一個結點的前驅結點為_head
char* _begin;//緩存的起始位置
char* _cur_begin;//用于分配結點內存的起始位置
};</pre>
實現2，使用stl的list
這個版本的實現來自 LeetCode discuss
class LRUCache{
size_t m_capacity;
unordered_map<int, list<pair<int, int>>::iterator> m_map; //m_map_iter->first: key, m_map_iter->second: list iterator;
list<pair<int, int>> m_list; //m_list_iter->first: key, m_list_iter->second: value;
public:
LRUCache(size_t capacity):m_capacity(capacity) {
}
int get(int key) {
auto found_iter = m_map.find(key);
if (found_iter == m_map.end()) //key doesn't exist
return -1;
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
return found_iter->second->second; //return value of the node
}
void set(int key, int value) {
auto found_iter = m_map.find(key);
if (found_iter != m_map.end()) //key exists
{
m_list.splice(m_list.begin(), m_list, found_iter->second); //move the node corresponding to key to front
found_iter->second->second = value; //update value of the node
return;
}
if (m_map.size() == m_capacity) //reached capacity
{
int key_to_del = m_list.back().first;
m_list.pop_back(); //remove node in list;
m_map.erase(key_to_del); //remove key in map
}
m_list.emplace_front(key, value); //create new node in list
m_map[key] = m_list.begin(); //create correspondence between key and node
}
};
通過兩個版本的實現，可以看到，使用stl的容器代碼非常簡潔，但也不是說自定義鏈表版本的實現就不好，如果從并發的角度來說，自定義的結構，在實現并發時，鎖的粒度會小一點，而直接使用stl容器，鎖的粒度為大一點，因為，使用stl，必須鎖定一個函數，而使用自定義結構可以只鎖定某個函數內部的某些操作，而且更方便實現無鎖并發。另外，從leetcode的測試結果來看，這兩個版本的性能差不多。
</div>