146. LRU 缓存

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

思路： 因为要求取值和存值时间复杂度都是O(1) 级别的，首先想到的数据结构是哈希表；那由于还需要加上淘汰机制，优化掉最近最少使用的数据，所以这里采取哈希+双向链表组合来实现，哈希表的key为传入的key ,val为node结点

class LRUCache {
    
    private Map<Integer, Node> map;
    private int capacity;//容量
    private Node first;//虚拟头结点
    private Node last;//虚拟尾结点

    public LRUCache(int capacity) {
       //初始化
       map = new HashMap(capacity);
       this.capacity = capacity;
       first = new Node();
       last = new Node();
       //绑定虚拟头节点和虚拟尾节点的关系
       first.next = last;
       last.prev = first;
    }
    
    //取值
    public int get(int key) {
      Node node = map.get(key);
      if(node==null) return -1;
      //来到这里说明有值，且被使用了；就需要删除当前节点，然后把节点添加到链表前面去
      removeNode(node);
      addAfterFirst(node);
      return node.value;
    }

    //存值
    public void put(int key, int value) {

        Node node =  map.get(key);
        if(node != null){//已经存过了，只需要更新即可
             node.value = value;
             removeNode(node);
        }else {//没存过 新增
            //满了 
            if(map.size()==capacity) {
             //删除最近最少使用的node和map中的kay
              removeNode(map.remove(last.prev.key));
            }
            //存起来
            node = new Node(key,value);
            map.put(key,node);
        }
        addAfterFirst(node);
    }

    void removeNode(Node node) {
       node.prev.next = node.next;
       node.next.prev = node.prev;
    }

    void addAfterFirst(Node node) {
       //node 与 first.next
        node.next = first.next;
        first.next.prev = node;
       //first 与 node
        first.next = node;
        node.prev = first;
    }

    private static class Node {
       public int key;
       public int value;
       public Node prev;
       public Node next;
       public Node(int key,int value){
            this.key = key;
            this.value = value;
       };
       public Node(){};
    }

}