Memcached的实现核心就是一个LRU
算法,它使用双端链表实现。
下面也是一个简单的用双端链表实现的单例LRU Cache,大家可以根据自己的需要添加一些方法。
class="java" name="code">package lruCache;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
public class LRUCache {
private static Map<Object, DoubleLinkedListNode> map = new HashMap<Object, DoubleLinkedListNode>();
private DoubleLinkedListNode head;
private DoubleLinkedListNode end;
private int len;
private int capacity;
private static LRUCache singleton = null;
public static LRUCache getInstance(int capacity){
if(null == singleton){
singleton = new LRUCache(capacity);
}
return singleton;
}
private LRUCache(int capacity) {
this.capacity = capacity;
len = 0;
}
public Object get(Object key) {
if(map.containsKey(key)){
DoubleLinkedListNode latest = map.get(key);
removeFromList(latest);
setHead(latest);
return latest.val;
}
else{
return null;
}
}
public void set(Object key, Object value) {
if (map.containsKey(key)) {
DoubleLinkedListNode oldNode = map.get(key);
oldNode.val = value;
removeFromList(oldNode);
setHead(oldNode);
} else {
DoubleLinkedListNode newNode =
new DoubleLinkedListNode(key, value);
if (len < capacity) {
setHead(newNode);
map.put(key, newNode);
len++;
} else {
map.remove(end.key);
end = end.pre;
if (end != null) {
end.post = null;
}
setHead(newNode);
map.put(key, newNode);
}
}
}
private void removeFromList(DoubleLinkedListNode node){
if(node.pre != null){
node.pre.post = node.post;
}
else{
head = node.post;
}
if(node.post != null){
node.post.pre = node.pre;
}
else{
end = node.pre;
}
}
private void setHead(DoubleLinkedListNode node){
node.post = head;
node.pre = null;
if (head != null) {
head.pre = node;
}
head = node;
if (end == null) {
end = node;
}
}
//返回当前Cache中key的集合
public Set<Object> keySet(){
Set<Object> res = new LinkedHashSet<Object>();
DoubleLinkedListNode cur = head;
while(null != cur){
res.add(cur.key);
cur = cur.post;
}
return res;
}
private class DoubleLinkedListNode{
Object key;
Object val;
DoubleLinkedListNode pre;
DoubleLinkedListNode post;
DoubleLinkedListNode(Object key, Object value){
this.key = key;
val = value;
}
}
}
测试类:
package lruCache;
import java.util.Set;
public class LRUCacheDemo {
public static void main(String[] args){
//新建一个容量为5的LRUCache
LRUCache lruCache = LRUCache.getInstance(5);
lruCache.set("1", "yi");
lruCache.set("1", "yiyi");
Set<Object> keySet = lruCache.keySet();
lruCache.set("2", "er");
lruCache.set("3", "san");
lruCache.set("4", "si");
lruCache.set("5", "wu");
lruCache.set("6", "liu");
Set<Object> keySet2 = lruCache.keySet();
}
}