双端链表实现LRUCache

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();
	}
}

评论

2 楼 xglv2013 2015-04-13  

liaokangli 写道

linkedhashmap 可以实现

对的 有不同种类的实现 可能效率也不尽相同 值得探讨一下

1 楼 liaokangli 2015-04-13  

linkedhashmap 可以实现