问题描述：
LRU算法:优先把那些最长时间没使用的对象置换掉。根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
JAVA实现：
测试：
public class preface {
public static void main(String[] args) {
LRUCache cache = new LRUCache();
cache.set(1, "one");
cache.set(2, "two");
cache.set(3, "three");
cache.set(5, "five");
cache.set(4, "five");
cache.get(2);
cache.set(6, "six");
cache.printCache();// 2,3,4,5,6
}
}
仓促之下写了个脑残版的，到头来也没能正确运行：
public class LRUCache {
private Map<Integer, pair> cache;
private int _cur; //计数
private int _capacity;
private int _nums = 0;
private heap _h;
public class pair implements Comparable {
public String value;
public int num;
public pair(int num, String value) {
this.num = num;
this.value = value;
}
@Override
public int compareTo(Object o) {
return num - ((pair) o).num;
}
}
//通过堆来对pairs进行排序
public class heap {
public pair[] pairs;
private int _cur;
public heap() {
pairs = new pair[5];
for (int i = 0; i < 5; ++i) {
pairs[i] = new pair(0, null);
}
_cur = 0;
}
//每次只能修改最上面的pair
public pair set(pair p) {
pair t = pairs[0];
pairs[0] = p;
return t;
}
public void insert(pair p) {
if (_cur < 5) {
pairs[_cur] = p;
}
++_cur;
}
public void sort() {
Arrays.sort(pairs);
}
public int find(pair p) {
for (int i = 0; i < 5; ++i) {
if (pairs[i] == p) { //==比较的是地址，equal比较的是值
return i;
}
}
return -1;
}
}
public LRUCache() {
_cur = 0;
_capacity = 0;
cache = new HashMap<Integer, pair>();
_h = new heap();
}
public String get(int key) {
++_cur;
if (cache.containsKey(key)) {
return cache.get(key).value;
}
return null;
}
public void set(int key, String value) {
++_cur;
if (!cache.containsKey(key)) {
++_nums;
pair p = new pair(_cur, value);
if (_nums == _capacity) {
pair t = _h.set(p);
for (Integer k:cache.keySet()) {
if (cache.get(k) == t) {
cache.remove(t);
break;
}
}
} else {
_h.insert(p);
}
cache.put(key, p);
} else {
pair p = cache.get(key);
int t = _h.find(p);
_h.pairs[t].num = _cur;
_h.pairs[t].value = value;
}
_h.sort();
}
public void printCache() {
System.out.println("print cache usage");
for (Integer key:cache.keySet()) {
pair p = cache.get(key);
System.out.println("Key:" + key + " Value:" + p.value + " num:" + p.num);
}
}
}
C++实现：
struct DoubleLinkList {
int key;
int value;
DoubleLinkList *next;
DoubleLinkList *pre;
DoubleLinkList(int k, int v) : key(k), value(v), next(NULL), pre(NULL) {};
};
class LRUCache{
public:
LRUCache(int capacity) {
size = capacity;
cacheMap.clear();
head = new DoubleLinkList(0, 0);
tail = new DoubleLinkList(0, 0);
head->next = tail;
tail->pre = head;
}
int get(int key) {
if (cacheMap.find(key) != cacheMap.end()) {
DoubleLinkList *p = cacheMap[key];
spliceNode(p);
addToFront(p);
return p->value;
}
return -1;
}
void set(int key, int value) {
if (cacheMap.find(key) == cacheMap.end()) {
DoubleLinkList *p = NULL;
if (cacheMap.size() == size) {
p = tail->pre;
cacheMap.erase(p->key);
p->key = key;
p->value = value;
spliceNode(p);
addToFront(p);
} else {
p = new DoubleLinkList(key, value);
addToFront(p);
}
cacheMap[key] = p;
} else {
DoubleLinkList *p = cacheMap[key];
p->value = value;
spliceNode(p);
addToFront(p);
}
}
private:
int size;
map<int, DoubleLinkList*> cacheMap;
DoubleLinkList *head, *tail;
void addToFront(DoubleLinkList *p) {
p->pre = head;
p->next = head->next;
head->next->pre = p;
head->next = p;
}
void spliceNode(DoubleLinkList *p) {
p->pre->next = p->next;
p->next->pre = p->pre;
}
};
用list代替双向链表：
struct CacheNode {
int key;
int value;
CacheNode(int k, int v) : key(k), value(v) {
}
};
class LRUCache{
public:
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
if (cacheMap.find(key) != cacheMap.end()) {
auto it = cacheMap[key];
cacheList.splice(cacheList.begin(), cacheList, it);
cacheMap[key] = cacheList.begin();
return cacheList.begin()->value;
} else {
return -1;
}
}
void set(int key, int value) {
if (cacheMap.find(key) == cacheMap.end()) {
if (cacheList.size() == size) {
cacheMap.erase(cacheList.back().key);
cacheList.pop_back();
}
cacheList.push_front(CacheNode(key, value));
cacheMap[key] = cacheList.begin();
} else {
auto it = cacheMap[key];
it->value = value;
cacheList.splice(cacheList.begin(), cacheList, it);
cacheMap[key] = cacheList.begin();
}
}
private:
int size;
list<CacheNode> cacheList;
unordered_map<int, list<CacheNode>::iterator > cacheMap;
};