LRU缓存介绍与实现
如何实现一个LRU呢？如果使用双向链表+Hash实现。
首先需求清楚：
-
什么是LRU；
-
需要哪些支持知识；
-
怎么使用这些基础知识实现；
-
如果高并发下怎么办；
-
反思一些基础知识。
什么是LRU：
就是最近最少访问。
需要哪些支持知识：
想想一个场景，LRU是不是就想电话记录或者微信记录，新的自动到上面，老的就慢慢下去了。
那是不是就想起了Linked。为什么没有使用linkedList呢？而是使用linkedMapHash。
我觉得：
linkedMapHash：就是linkedList+HashMap。 linkedList用来维护顺序，HashMap用来存储数据。通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。
怎么使用这些基础知识实现
参考：http://blog.csdn.net/beiyeqingteng/article/details/7010411
思路：
-
可以顺序查询；
-
访问不过是插入还是查询都可以，该值自动放到第一位，后面的值自动后退移位；
怎么做到上述点呢？如果使用linkedMapHash貌似一下就解决了。
LinkedHashMap accessOrder设为true，按照访问顺序排序
但是如果让自己实现呢？
public class LRUCache {
private int cacheSize;
private Hashtable<Object, Entry> nodes;//缓存容器
private int currentSize;
private Entry first;//链表头
private Entry last;//链表尾
public LRUCache(int i) {
currentSize = 0;
cacheSize = i;
nodes = new Hashtable<Object, Entry>(i);//缓存容器
}
/**
* 获取缓存中对象,并把它放在最前面
*/
public Entry get(Object key) {
Entry node = nodes.get(key);
if (node != null) {
moveToHead(node);
return node;
} else {
return null;
}
}
/**
* 添加 entry到hashtable, 并把entry
*/
public void put(Object key, Object value) {
//先查看hashtable是否存在该entry, 如果存在，则只更新其value
Entry node = nodes.get(key);
if (node == null) {
//缓存容器是否已经超过大小.
if (currentSize >= cacheSize) {
nodes.remove(last.key);
removeLast();
} else {
currentSize++;
}
node = new Entry();
}
node.value = value;
//将最新使用的节点放到链表头，表示最新使用的.
moveToHead(node);
nodes.put(key, node);
}
/**
* 将entry删除, 注意：删除操作只有在cache满了才会被执行
*/
public void remove(Object key) {
Entry node = nodes.get(key);
//在链表中删除
if (node != null) {
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (last == node)
last = node.prev;
if (first == node)
first = node.next;
}
//在hashtable中删除
nodes.remove(key);
}
/**
* 删除链表尾部节点，即使用最后 使用的entry
*/
private void removeLast() {
//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
if (last != null) {
if (last.prev != null)
last.prev.next = null;
else
first = null;
last = last.prev;
}
}
/**
* 移动到链表头，表示这个节点是最新使用过的
*/
private void moveToHead(Entry node) {
if (node == first)
return;
if (node.prev != null)
node.prev.next = node.next;
if (node.next != null)
node.next.prev = node.prev;
if (last == node)
last = node.prev;
if (first != null) {
node.next = first;
first.prev = node;
}
first = node;
node.prev = null;
if (last == null)
last = first;
}
/*
* 清空缓存
*/
public void clear() {
first = null;
last = null;
currentSize = 0;
}
}
class Entry {
Entry prev;//前一节点
Entry next;//后一节点
Object value;//值
Object key;//键
} 思路就是：双链表 + hashtable实现
为什么要用hashtable呢？
我觉得还是Hashmap也行。
在这个代码中：双向链表是自定义的：
-
class Entry {
-
Entry prev;//前一节点
-
Entry next;//后一节点
-
Object value;//值
-
Object key;//键
-
}
主要核心逻辑是被当访问后，需要将此值放到头部。
实现代码：moveToHead
上一篇： freemarker环境搭建(一)
下一篇： SpringMVC基于注解开发