LRU缓存机制

问题：获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
例子:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解析1:HashMap+双向链表。根据要求，可以实现put时，若不存在key相同的，将newNode插入双向链表head的后继，即头节点，若此时size大于capacity则将尾节点和其kv删除。否则，将原先节点提到头节点处，将value更新。实现get时，直接输出value值并且将该key对应的节点提到头节点处。

代码:

import java.util.Hashtable;
public class LRUCache {

  class DLinkedNode {//定义节点
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
  }

  private void addNode(DLinkedNode node) {//增加node至头节点处操作
    /**
     *新的节点总在head节点后
     */
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
  }

  private void removeNode(DLinkedNode node){
    /**
     * 删除节点的操作
     */
    DLinkedNode prev = node.prev;
    DLinkedNode next = node.next;

    prev.next = next;
    next.prev = prev;
  }

  private void moveToHead(DLinkedNode node){
    /**
     * 更新当前节点位置至头节点处
     */
    removeNode(node);
    addNode(node);
  }

  private DLinkedNode popTail() {
    /**
     * 将尾节点tail的前驱节点输出(同时删除该节点)
     */
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
  }

  private Hashtable<Integer, DLinkedNode> cache =
          new Hashtable<Integer, DLinkedNode>();//定义一个Hashtable(key,双向链表)
  private int size;
  private int capacity;
  private DLinkedNode head, tail;

  public LRUCache(int capacity) {//构造函数，造出head，tail相互指向
    this.size = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    // head.prev = null;

    tail = new DLinkedNode();
    // tail.next = null;

    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // 更新节点的位置
    moveToHead(node);

    return node.value;
  }

  public void put(int key, int value) {
    DLinkedNode node = cache.get(key);//查看当前链表中key对应的节点

    if(node == null) {//如果链表中无此节点
      DLinkedNode newNode = new DLinkedNode();
      newNode.key = key;
      newNode.value = value;

      cache.put(key, newNode);
      addNode(newNode);//加入链表

      ++size;//长度加一

      if(size > capacity) {//超出了容量
        // pop the tail
        DLinkedNode tail = popTail();//将尾部节点删除
        cache.remove(tail.key);//在hashtable中将其对应的kv删除
        --size;
      }
    } else {
      //链表中有此节点则更新value.
      node.value = value;
      moveToHead(node);//移至头节点
    }
  }
}

/**
 * LRUCache 对象会以如下语句构造和调用:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

解析2:LinkedHashMap的使用。需要对LinkedHashMap有深刻的了解。有序的hashMap，get过一次，就变到首端（直接达到了上述的效果，实际上上面就是对LinkedHashMap的实现）。只要在put的时候是否需要将最老节点去掉的条件改成size和capacity的大小关系就可以了。

代码:

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key,-1);//Map中的方法，找到了返回value，没有就返回-1
    }

    public void put(int key, int value) {
        super.put(key,value);
    }
    @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}