一.前沿学习或工作时，接触了LRU相关的缓存策略列，想知道下一个LRU。 在网上谷歌写了相关内容后，自己也写了简单的LRU实现。 (当然，实现这个算法有很多，策略列也不固定，需要根据具体的业务和权衡制定合理的算法策略列。 )写blog的简要记录。
2 .用一个教材案例展示了LRU的原理，假设内存只能容纳3个页面，按照7、0、1、2、0、3、0、4的顺序访问页面。 假设内存将访问时间描述为堆栈，LRU的工作方式如下： 也就是说，上面的是最近访问的，下面的是在最远的时间访问的。
也就是说，要设计需要插入(get )要素的) insert )要素的缓存系统，可以和hash ) get时间复杂度o )1)链表) insert时间复杂度o )1)的方式组合来实现
基于HashMap和双向链表实现LRU总体设计思路。 首先，有head和tail这两个特殊的要素，分别表示双向链表的“头”和“尾”。 一种hashmap基于key隐藏在特定元素中。 同时，缓存容量不能为无穷大。 在达到最大缓存后，有一个清理元素的过程。 链表的处理有get和set两种操作
get :获取元素的操作。 判断hashmap中是否存在命中的元素，如果存在，则将该元素的位置调整到链表的开头位置。 不包括头和鞋。 调整位置过程为：1.从原始位置删除要素，2 .将要素插入链首； 如果不能命中，则返回null
set:要素的插入操作是在插入前判断要素是否存在(根据hashmap图可知)，如果存在，则更新要素值，将该要素的位置调整为链表的开头位置(同上)； 如果不存在，则将元素插入到链的开头，同时判断是否命中缓存容量，如果达到缓存容量，则删除链表末尾的元素。 hashmap也同样更新并删除。 可以将此操作视为在get操作中将元素从其原始位置删除的特例。)
java代码如下：
import java.util.HashMap； import java.util.Map；/* * * createdbyldxpc */publicclasslrucachek，V { private MapK，DLinkedNodeK，V cache=new HashMapK，DLinkedNodeK，v private int maxCacheCapacity； private DLinkedNodeK，V head； private DLinkedNodeK，V tail； //初始化双链路列表private void init () { head=new DLinkedNodeK，v )； tail=new DLinkedNodeK，v (； head.pre=null； head.post=tail； tail.pre=head； tail.post=null； } privatelrucache (intmaxcachecapacityvalue ) maxcachecapacity=maxcachecapacityvalue； init (； } privatevoidremovenode ({ dlinkednodek，V value ) dlinkednodek，V preNode=value.pre； DLinkedNodeK，V postNode=value.post； preNode.post=postNode； postNode.pre=preNode； adjustcurrentcachecapacity(-1； } privatevoidaddnode ({ dlinkednodek，V value ) dlinkednodek，V headPostNode=head.post； value.post=headPostNode； value.pre=head； head.post=value； headPostNode.pre=value； adjustcurrentcachecapacity(1)； } privatevoidadjustcurrentcachecapacity (int count ) currentcachecapacity=currentcachecapacitycount； } privatevoidmovenodetohead (dlinkednodek，
V> value){ removeNode(value); addNode(value); } private void set(K k,V v){ DLinkedNode<K,V> value = cache.get(k); if(value == null){ DLinkedNode<K,V> newNode = new DLinkedNode<K,V>(k,v); cache.put(k,newNode); addNode(newNode); if(currentCacheCapacity > maxCacheCapacity){ DLinkedNode<K,V> lastNode = tail.pre; removeNode(lastNode); cache.remove(lastNode.key); } }else{ value.value = v; moveNodeToHead(value); } } private V get(K k){ DLinkedNode<K,V> value = cache.get(k); if(value != null){ moveNodeToHead(value); return value.value; }else{ return null; } } private void printLink(){ StringBuilder builder = new StringBuilder(); DLinkedNode<K,V> node = head; while(node != null){ builder.append(node.key+"-->"); node = node.post; } System.out.println(builder.toString()); } public static void main(String[] args){ LRUCache<String,Integer> lruCache = new LRUCache<>(3); lruCache.set("7",7); lruCache.printLink(); lruCache.set("0",0); lruCache.printLink(); lruCache.set("1",1); lruCache.printLink(); lruCache.set("2",2); lruCache.printLink(); lruCache.get("0"); lruCache.printLink(); lruCache.set("3",3); lruCache.printLink(); lruCache.get("0"); lruCache.printLink(); lruCache.set("4",4); lruCache.printLink(); }}public class DLinkedNode<K,V> { public DLinkedNode(){} public DLinkedNode(K k,V initValue){ key = k; value = initValue; } K key; V value; DLinkedNode pre; DLinkedNode post;}
打印结果：
null-->7-->null-->
null-->0-->7-->null-->
null-->1-->0-->7-->null-->
null-->2-->1-->0-->null-->
null-->0-->2-->1-->null-->
null-->3-->0-->2-->null-->
null-->0-->3-->2-->null-->
null-->4-->0-->3-->null-->
（前后两个null表示head 元素和tail 元素）
该算法还需待完善的地方：
1. 居于hashmap+双向链表的方式 是牺牲了内层（hashmap pre post ）来实现的，居然做缓存那内存的使用率肯定是很重要的。 那双链表可以改用单链表吗？即DLinkedNode仅仅 有post, 将pre去掉。
2. LRU算法认为 最近访问过的元素将来访问的概率更大，这仅仅是一种概率。 为了完美感觉可以将cache的元素设置具有TTL的功能，配合最大缓存容量清理一些长时间没访问的元素
3. 将程序是线程不安全的，如果是多线程，相应的添加锁机制