LRU算法学习总结

一.前沿

     之前在学习或者工作中，接触到LRU相关的缓存策列，于是想着了解下LRU。在网上google了下相关内容后 自己也写了一个简单的LRU实现（当然实现该算法有很多，策列也不一样是固定的，需要根据具体的业务及权衡做出合理的算法策列），写一篇blog简单的记录下

二.LRU原理

      用一个教材案例来演示LRU原理，假设内存只能容纳3个页大小，按照7 、0、1、 2、 0、 3、 0、 4 的次序访问页。假设内存按照栈的方式来 描述访问时间（即在上面的是最近访问的，在下面的是最远时间访问的），LRU工作如下：

    设计一个 即要取（get）元素，又需要插入（insert）元素的缓存系统，我们可以结合hash（get 时间复杂度O(1) ）+ 链表(insert 时间复杂度O(1) ) 的方式来实现

3. 基于HashMap 和 双向链表 来实现LRU

       整体设计思路：首先有两个特殊的元素：head 以及tail ，分别表示双向链表的“头”和“尾”。有一个hashmap是根据key来隐射到具体元素的。同时缓存容量不能无限大，有一个达到最大缓存后清理元素的过程。对链表的处理有两个操作：get和set

       get：获取元素的操作 ，通过hashmap 确定是否 有命中的元素，如果可以命中，将该元素的位置调整到链表首位置（head 和 tail 不包括在内），调整位置的过程可以 分解为： 1.将元素从原来的位置删除，2.将元素insert 到 链首  ； 如果不能命中返回null

       set:  插入元素的操作 ，插入前先判断 元素是否存在（hashmap映射可知），如果存在 更新元素值并且将该元素的位置调整到链表首位置（同上）； 如果不存在，将元素insert 到链首，同时判断是否打到缓存容量，如果达到缓存容量，将链表尾元素 删除（hashmap同样也更新删除，该操作可以看作是get 操作中将元素从原来位置删除 的特例啦）

        java代码如下：

import java.util.HashMap;
import java.util.Map;

/**
 * Created by ldxPC
 */
public class LRUCache<K,V> {

  private Map<K,DLinkedNode<K,V>> cache = new HashMap<K, DLinkedNode<K,V>>();


  private int currentCacheCapacity;

  private int maxCacheCapacity ;

  private DLinkedNode<K,V> head;

  private DLinkedNode<K,V> tail ;

  //构造初始化双链表
  private void init(){
       head = new DLinkedNode<K,V>();
       tail = new DLinkedNode<K,V>();
       head.pre=null;
       head.post = tail;

       tail.pre = head;
       tail.post = null;
  }

  private LRUCache(int maxCacheCapacityValue){
       maxCacheCapacity = maxCacheCapacityValue;
       init();
  }

  private void removeNode(DLinkedNode<K,V> value){
      DLinkedNode<K,V> preNode = value.pre;
      DLinkedNode<K,V> postNode = value.post;
      preNode.post= postNode;
      postNode.pre = preNode;
      adjustCurrentCacheCapacity(-1);
  }

  private  void addNode(DLinkedNode<K,V> value){
      DLinkedNode<K,V> headPostNode = head.post;
      value.post = headPostNode;
      value.pre  = head;

      head.post = value;
      headPostNode.pre = value;
      adjustCurrentCacheCapacity(1);
  }


  private void adjustCurrentCacheCapacity(int count){
      currentCacheCapacity = currentCacheCapacity + count;
  }

  private void moveNodeToHead(DLinkedNode<K,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. 将程序是线程不安全的，如果是多线程，相应的添加锁机制