Memcached的实现核心就是一个LRU算法,它使用双端链表实现。
下面也是一个简单的用双端链表实现的单例LRU Cache,大家可以根据自己的需要添加一些方法。
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();
}
}
分享到:
相关推荐
双端链表和双向链表Java代码
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
主要介绍了Java模拟单链表和双端链表数据结构的实例,注意这里的双端链表不是双向链表,是在单链表的基础上保存有对最后一个链接点的引用,需要的朋友可以参考下
主要介绍了Java数据结构之双端链表原理与实现方法,简单描述了双端链表的概念、原理并结合实例形式分析了java实现双端链表的相关操作技巧,需要的朋友可以参考下
栈关于数组与链表的实现,linux c语言
链表实现集合运算 链表实现集合交并差运算
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
数据结构 课程设计 用链表实现集合并集 c++
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
c++,算法链表实现一元多项式相加,通过链表实现,非常好的一个程序
C语言链表实现的贪吃蛇小游戏。.zipC语言链表实现的贪吃蛇小游戏。.zipC语言链表实现的贪吃蛇小游戏。.zipC语言链表实现的贪吃蛇小游戏。.zipC语言链表实现的贪吃蛇小游戏。.zipC语言链表实现的贪吃蛇小游戏。.zipC...
用链表实现线性表java用链表实现线性表
栈的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例
链表 实现 c++ cpp 数据结构 作业 链表 实现 c++ cpp 数据结构 作业
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
用C语言链表实现进程转换,阻塞变就绪,就绪变执行,执行变阻塞三种状态的转换
简单的用链表来实现图书的增删该查功能,更能明白链表的原理……
利用双向循环链表作为储存结构设计并实现一个通讯录程序。可以实现信息的添加、插入、删除、查询和统计等功能 1.2 课程设计要求 (1) 每条信息至少包含:姓名(name)、街道(street)、城市(city)、邮编、(eip...
大学期间用C语言链表实现的一个图书管理系统,主要功能有 a. 设备申请。由专业人员填写“申请表”送交领导批准购买。 b. 设备入库。新设备购入后要立即进行设备登记(包括类别、设备名、型号、规格、单价、数量、...
用链表实现的职工管理软件 ( C+ + )