1、原理

image.png
维护一个双向链表，最新访问或添加的元素插入到链表head或者tail，
假设采用尾插法，那么最新的元素都在尾部，当LRU缓存容量满的时候，就只需要把头部节点移除即可
当有查询操作，则根据key找到对应的node，并将node移到尾部，时间复杂度为O(1)

2、手写实现

  1. package algo;
  3. import java.util.Hashtable;
  5. /**
  6.  * TODO 此处填写class用途
  7.  *
  8.  * @author weixin
  9.  * @date 2020/5/9 16:25
  10.  **/
  11. public class LRUCache {
  13.    class DLinkedNode{
  14.     int key;
  15.     int value;
  16.     DLinkedNode prev;
  17.     DLinkedNode next;
  18.     public DLinkedNode(){};
  19.     public DLinkedNode(int key, int value){
  20.       super();
  21.       this.key = key;
  22.       this.value = value;
  23.     }
  25.     @Override
  26.     public String toString() {
  27.       StringBuilder stringBuilder = new StringBuilder();
  28.       stringBuilder
  29.           .append("DLinkedNode{ key=")
  30.           .append(key)
  31.           .append(", value=")
  32.           .append(value)
  33.           .append(", prev=")
  34.           .append(prev == null ? null : prev.key)
  35.           .append(", next=")
  36.           .append(next == null ? null : next.key);
  37.       return stringBuilder.toString();
  38.     }
  39.   }
  42.   /**
  43.    * 缓存当前大小
  44.    */
  45.   private int size;
  46.   /**
  47.    * 缓存容量
  48.    */
  49.   private int capacity;
  50.   private DLinkedNode head;
  52.   private DLinkedNode tail;
  54.   private Hashtable<Integer,DLinkedNode> cache;
  56.   public LRUCache(int capacity) {
  57.     this.size = 0;
  58.     this.capacity = capacity;
  59.     head = new DLinkedNode();
  60.     tail = new DLinkedNode();
  61.     //构建一个双向链表
  62.     head.next = tail;
  63.     tail.prev = head;
  64.     cache = new Hashtable<Integer, DLinkedNode>();
  65.   }
  67.   public int get(int key) {
  68.     DLinkedNode node = cache.get(key);
  70.     if(null == node){
  71.       return -1;
  72.     }
  73.     //将node移到尾部
  74.     move2Tail(node);
  75.     return node.value;
  76.   }
  78.   private void move2Tail(DLinkedNode node){
  79.     node.next = tail;
  80.     node.prev = tail.prev;
  81.     tail.prev.next = node;
  82.     tail.prev = node;
  83.   }
  85.   private void popNode(DLinkedNode node){
  86.     System.out.println("removeNode: "+node);
  87.     DLinkedNode second = node.next;
  88.     head.next = second;
  89.     second.prev = head;
  90.     node.next = null;
  91.     node.prev = null;
  93.   }
  95.   public void put(int key, int value) {
  96.     DLinkedNode node = cache.get(key);
  97.     //存在则覆盖
  98.     if(node != null){
  99.       node.value = value;
  100.       cache.put(key,node);
  101.       return;
  102.     }
  103.     size++;
  104.     if(size>capacity){
  105.       popNode(head.next);
  106.     }
  108.     //新增node
  109.     DLinkedNode nNode = new DLinkedNode(key,value);
  110.     addNode(nNode);
  111.     cache.put(key,nNode);
  112.     //超过容量，删除头部节点
  113.   }
  116.   private void addNode(DLinkedNode node){
  117.     //添加到尾部
  118.     tail.prev.next = node;
  119.     node.prev = tail.prev;
  120.     node.next= tail;
  121.     tail.prev = node;
  122.     System.out.println("add node: "+ node);
  123.   }
  125.   private void removeNode(DLinkedNode node){
  126.     head.next = node.next;
  127.     node.next.prev = head;
  128.     node.next = null;
  129.     node.prev = null;
  130.   }
  132.   public static void main(String[] args) {
  133.    LRUCache lruCache = new LRUCache(4);
  134.     for (int i = 1; i<10; i++) {
  135.       lruCache.put(i,i);
  137.       System.out.println(lruCache.get(i));
  138.     }
  139.   }
  140. }