LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
实现思路：
hashtable + 双向链表
时间复杂度： 插入，查找，删除：O（1）
空间使用情况： O（N）
:一个链表存储K个数据（stl的hash_map实际占的空间比较大）。
运行环境：
linux:redhat ,
fedora ,centos等（理论上ubuntu , debian,mac os等也可以运行）
代码：
[cpp]
view plaincopy
#ifndef __LRUCACHE_H__
#define
__LRUCACHE_H__
#include
#include
#include
#include
using
namespace __gnu_cxx;
template
struct Node{
K
key;
D data;
Node *prev,
*next;
};
template
class
LRUCache{
public:
LRUCache（size_t size , bool is_pthread_safe
= false）{
if（size <= 0）
size = 1024;
pthread_safe
=
is_pthread_safe;
if（pthread_safe）
pthread_mutex_init（&cached_mutex
, NULL）；
entries = new Node[size];
for（size_t i = 0; i <
size; ++i）
cached_entries.push_back（entries + i）；
head = new
Node;
tail = new Node;
head->prev =
NULL;
head->next = tail;
tail->prev =
head;
tail->next =
NULL;
}
~LRUCache（）{
if（pthread_safe）
pthread_mutex_destroy（&cached_mutex）；
delete
head;
delete tail;
delete[] entries;
}
void
Put（K key, D data）；
D Get（K key）；
private:
void
cached_lock（void）{
if（pthread_safe）
pthread_mutex_lock（&cached_mutex）；
}
void
cached_unlock（void）{
if（pthread_safe）
pthread_mutex_unlock（&cached_mutex）；
}
void
detach（Node* node）{
node->prev->next =
node->next;
node->next->prev =
node->prev;
}
void attach（Node*
node）{
node->prev = head;
node->next =
head->next;
head->next = node;
node->next->prev =
node;
}
private:
hash_map* >
cached_map;
vector* > cached_entries;
Node * head,
*tail;
Node * entries;
bool
pthread_safe;
pthread_mutex_t
cached_mutex;
};
template
void LRUCache::Put（K key ,
D data）{
cached_lock（）；
Node *node =
cached_map[key];
if（node）{
detach（node）；
node->data
=
data;
attach（node）；
}
else{
if（cached_entries.empty（））{
node
=
tail->prev;
detach（node）；
cached_map.erase（node->key）；
}
else{
node
=
cached_entries.back（）；
cached_entries.pop_back（）；
}
node->key
= key;
node->data = data;
cached_map[key] =
node;
attach（node）；
}
cached_unlock（）；
}
template
D
LRUCache::Get（K key）{
cached_lock（）；
Node *node =
cached_map[key];
if（node）{
detach（node）；
attach（node）；
cached_unlock（）；
return
node->data;
}
else{
cached_unlock（）；
return
D（）；
}
}
#endif
测试用例：
[cpp] view
plaincopy
/*
Compile:
g++ -o app app.cpp LRUCache.cpp
-lpthread
Run:
./app
*/
#include
#include
#include
"LRUCache.h"
using namespace
std;
int
main（void）{
//int k = 10 ,
// max =
100;
int k = 100000 ,
max = 1000000;
LRUCache *
lru_cache = new LRUCache（k , true）；
int tmp = 0;
for（int i = 0
; i < 2*k ; ++i）{
tmp = rand（） %
max;
lru_cache->Put（tmp, tmp +
1000000）；
cout<
}
for（int i = 0 ; i < k ;
++i）{
tmp = rand（） % max;
if（lru_cache->Get（tmp） ==
0）
cout《"miss : "<
else
cout《"hit : "<
www.yzyedu.com