简单LRU缓存实现
链表保存键值，由于没有权值策略，简单的将当前访问过的节点放到链表头部，则存在如下问题：
在周期性访问中，某个周期中存在一部分数据仅仅只访问了一次，则最终导致缓存中的数据都是无效的数据，而将频繁访问的数据排除了。在实际应用中，这种简单策略不适用。
TestCode
package org.jf.alg.lru;import java.util.HashMap;import java.util.Map;/** * * LRU 简单实现 * 双向链表+HashMap * @author chenjf * */public class LRUCache {private KeyNode head;//key值的链表头 (包含数据)private KeyNode tail;//key值的链表尾 (包含数据)private int capacity;private int size;private Map<Object,CacheObject> map = new HashMap<Object,CacheObject>();public LRUCache(int capacity){this.capacity=capacity;}public void put(Object key,Object value){if(value==null)return;Object obj = this.get(key);if(obj!=null) return;KeyNode node = new KeyNode(key);CacheObject cache_obj = new CacheObject(node,value);map.put(key, cache_obj);if(head==null){head = node;tail = node;size++;}else{head.previous = node;node.next = head;head = node;size++;if(size>capacity){remove(tail.key);}}}public Object remove(Object key){Object data = null;Object obj = map.remove(key);if(obj!=null){CacheObject cache_obj = (CacheObject)obj;KeyNode node = cache_obj.keyNode;if(size==1){head = null;tail = null;}else{if(node.equals(head)){if(head.next!=null)//not tailhead.next.previous = null; head = head.next; node.next = null;}else if(node.equals(tail)){tail = node.previous;if(tail!=null){tail.next = null;}node.previous = null;}else// not head and tail{node.previous.next=node.next;node.next.previous=node.previous;node.previous=null;node.next=null;}}data = cache_obj.data;size--;}return data;}public Object get(Object key){Object data = null;Object obj = map.get(key);if(obj!=null){CacheObject cache_obj = (CacheObject)obj;KeyNode node = cache_obj.keyNode;if(!node.equals(head))//if node is head, nothing to do{node.previous.next = node.next;if(node.next!=null)node.next.previous = node.previous;else// node is tailtail = node.previous;node.next = head;head.previous = node;node.previous = null;head = node;}data = cache_obj.data;}return data;}public void clear(){head = null;tail = null;size = 0;map.clear();}public int size(){return this.size;}public int getCapacity(){return this.capacity;}/** * * for debug */public void printFrontTrace(){//print front from head to tailif(head!=null){KeyNode node = head;while(node!=null){System.out.print("-->"+node.key+"["+map.get(node.key).data+"]");node=node.next;}}}public void printBackwardTrace(){if(tail!=null){KeyNode node = tail;while(node!=null){System.out.print("<--"+node.key+"["+map.get(node.key).data+"]");node=node.previous;}}}/****************************inner class from object store**************************************/class KeyNode {KeyNode previous;KeyNode next;Object key; public KeyNode(Object key) {this.key = key; }} class CacheObject{public CacheObject(KeyNode node,Object data){keyNode = node;this.data = data;}KeyNode keyNode;Object data;}}