缓存策略之LRU实现及分析
- LRU定义
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。 LRU Cache 的替换原则就是将最近最少使用的内容替换掉 Least recently used. 可以理解为， 淘汰不常用的数据
2. 数据更新测量
基于双链表的LRU算法的实现，
它的原理： 将Cache的所有位置都用双连表连接起来，
a 访问操作：
当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，
b 插入操作
1 如果cache 未满 新加入的Cache直接加到链表头中。
2 当需要替换内容时候，链表的最后位置就是最少被命中的位置，
我们只需要淘汰链表最后的部分即可。
结果：
经常被访问数据在前面
不经常被访问数据在后面
3 代码实现
我们用一个对象来表示Cache，并实现双链表，
Java代码
public class LRUCache {
/**
* 链表节点
* @author Administrator
*
*/
class CacheNode {
……
}
private int cacheSize;//缓存大小
private Hashtable nodes;//缓存容器
private int currentSize;//当前缓存对象数量
private CacheNode first;//(实现双链表)链表头
private CacheNode last;//(实现双链表)链表尾
} 下面给出完整的实现，这个类也被Tomcat所使用（ org.apache.tomcat.util.collections.LRUCache），但是在tomcat6.x版本中，已经被弃用，使用另外其他的缓存类来替代它。
Java代码
public class LRUCache {
/**
* 链表节点
* @author Administrator
*
*/
class CacheNode {
CacheNode prev;//前一节点
CacheNode next;//后一节点
Object value;//值
Object key;//键
CacheNode() {
}
}
public LRUCache(int i) {
currentSize = 0;
cacheSize = i;
nodes = new Hashtable(i);//缓存容器
}
/**
* 获取缓存中对象
* @param key
* @return
*/
public Object get(Object key) {
CacheNode node = (CacheNode) nodes.get(key);
if (node != null) {
moveToHead(node);
return node.value;
} else {
return null;
}
}
/**
* 添加缓存
* @param key
* @param value
*/
public void put(Object key, Object value) {
CacheNode node = (CacheNode) nodes.get(key);
if (node == null) {
//缓存容器是否已经超过大小.
if (currentSize >= cacheSize) {
if (last != null)//将最少使用的删除
nodes.remove(last.key);
removeLast();
} else {
currentSize++;
}
node = new CacheNode();
}
node.value = value;
node.key = key;
//将最新使用的节点放到链表头，表示最新使用的.
moveToHead(node);
nodes.put(key, node);
}
/**
* 将缓存删除
* @param key
* @return
*/
public Object remove(Object key) {
CacheNode node = (CacheNode) 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;
}
return node;
}
public void clear() {
first = null;
last = null;
}
/**
* 删除链表尾部节点
* 表示 删除最少使用的缓存对象
*/
private void removeLast() {
//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
if (last != null) {
if (last.prev != null)
last.prev.next = null;
else
first = null;
last = last.prev;
}
}
/**
* 移动到链表头，表示这个节点是最新使用过的
* @param node
*/
private void moveToHead(CacheNode 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;
}
private int cacheSize;
private Hashtable nodes;//缓存容器
private int currentSize;
private CacheNode first;//链表头
private CacheNode last;//链表尾
} 4 性能分析：
lur 算法 时间复杂度是 o（1）
为啥不是o(n)
hashtable作为索引 --快速访问
list链表 ---存储有序数据
5 扩展 （hashtable+list方式）
Q1 用redis数据结构 zset结构如何实现的 请问是用红黑树吗 ?
A:不是
1 hash--快速查找 key-value 2 链表方式 --保证数据顺序
KIPLIST 编码的有序集
当使用 REDIS_ENCODING_SKIPLIST 编码时， 有序集元素由 redis.h/zset 结构来保存：
/* * 有序集 */typedef struct zset {
// 字典
dict *dict;
// 跳跃表
zskiplist *zsl;} zset;采用复合结构,
字典维护了name=>score的映射表,
而跳跃表则维护了按score排序的列表. 按name和按score的范围查询都天然支持.
Q2 为什么用能map 代替（hash+list方式） 两个结构表示多麻烦呀
STL的map底层是用红黑树实现的，查找时间复杂度是log(n)； STL的hash_map底层是用hash表存储的，查询时间复杂度是O(1)重复记录 最坏情况o(n)
A2:
map在数量大时候缺点
一般应用情况下，我们保存的数据不超过100万份，查找的频繁程度不高情况下使用map性能比较好；
而保存的数据较多时（超过100万），查找频繁时使用hash_map的性能就高于map了
参考
1 http://redisbook.readthedocs.io/en/latest/datatype/sorted_set.html