本文整理自一下两篇博客： http://my.oschina.net/u/866190/blog/188712
Cache简介：
Cache(高速缓存)， 一个在计算机中几乎随时接触的概念。CPU中Cache能极大提高存取数据和指令的时间，让整个存储器(Cache+内存)既有Cache的高速度，又能有内存的大容量；操作系统中的内存page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存，从而提高访问速度。Cache的算法设计常见的有FIFO(first in first out，先进先出)、LRU(least recently used，最近最少使用)和LFU（Least Frequently userd，最不经常使用)。
插入：
更新：
和查询相似
删除：
从双向链表和Hashmap中同时删除对应的记录。
实现方式
参考实现：Apache jcs
1）首先我们需要一个双向链表，自然地，我们需要定义双向链表的节点：DoubleLinkListNode，DoubleLinkList
DoubleLinkListNode implements Serializable{private Object value;public DoubleLinkListNode next;public DoubleLinkListNode prev;DoubleLinkListNode(Object value){this.value = value;}public Object getValue() {return value;}}
对于 DoubleLinkList ,我们需要同步对节点的各种读写操作：
public class DoubleLinkList {private int size = 0;private DoubleLinkListNode first;private DoubleLinkListNode last;public DoubleLinkList(){super();}addLast(DoubleLinkListNode me){if (first == null) {first = me;}else{last.next = me;me.prev = last;}last = me;size++;}addFirtst(DoubleLinkListNode me){if (last == null) {last = me;}else{first.next = me;me.prev = first;}first = me;size++;}DoubleLinkListNode getLast(){return last;}DoubleLinkListNode getFirst(){return first;}remove(DoubleLinkListNode me){if(me.next == null){//删除尾节点if (me.prev == null) {( me == first && me == last ){first = last = null;}} else {last = me.prev;last.next = null;me.prev = null;// gc 回收需要}}else if(me.prev == null){// 头结点first = me.next;first.prev = null;me.next = null;}else{// 中间节点me.prev.next = me.next;me.next.prev = me.prev;me.prev = me.next = null;}size–;return true;}removeAll(){for(DoubleLinkListNode me=first;me!=null;){if (me.prev != null) {me.prev = null;}DoubleLinkListNode next = me.next;me = next;}first = last = null;size = 0;return true;}DoubleLinkListNode removeLast(){DoubleLinkListNode temp = last;if (last != null) {remove(last);}return temp;}makeFirst(DoubleLinkListNode node){if (node.prev == null) {// already the first node , or not a nodereturn;}node.prev.next = node.next;if (node.next == null) {// last but the firstlast = node.prev;last.next = null;}else {//neither the last or the firstnode.next.prev = node.prev;}first.prev = node;node.next = first;node.prev = null;first = node;}size(){return size;}}
2）双向链表实现了，接着我们需要实现一个自定义的 LRUMap，根据 key 来存储 DoubleLinkListNode。这样我们就可以借助map 的hash 表来查询相对应的值。
·在给出实现之前，我们也许回想到，map 的键值对中，key 自己创建，而 value 就是 DoubleLinkListNode，来实现这个map，在 put 的时候，根据需要调整 cache 的容量即可（LRU 算法）。
如果是这样想得，那我们再反过来想，其实 map 本事就是一个容器，可直接用作 cache，直接使用 Map(Object key,Object value) 比使用 Map(Object key,doubleLinkListNode node)更好，，可这样做的时候，就会出现一个问题，当我们需要删除一个对象，准确地说，是删除一个最近最久没有被使用过得对象，这样的操作原始的 map 结果是实现不了的；或许更进一步，你会想到，我们可以 map 里的每一个对象添加一个时间标记，这样在删除的时候，需要遍历每一个对象，找出时间标记为最早的那一个，直接就删除它（这样做，效率会很不好，需要O(n) 的时间）。说道这里，其实就是想说，借助双链表就是为了快速删除最近最久未被使用的对象，所以我们需要搭建一个描述符，来关联 hashMap 和 双联表之间的关系。
先实现一个 map 键值对描述符，如下： public class LRUElementDescriptor extends DoubleLinkListNode {private Object key;public LRUElementDescriptor(Object key,Object value){super(value);this.key = key;}public Object getKey() {return key;}public void setKey(Object key) {this.key = key;}}
接着实现一下LRUMap 基本的操作，如下：
做事不怕难，自无难人事。
