Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

    get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
    put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

    The cache is initialized with a positive capacity.

    Follow up:
    Could you do both operations in O(1) time complexity?

    Example:

    1. LRUCache cache = new LRUCache( 2 /* capacity */ );
    3. cache.put(1, 1);
    4. cache.put(2, 2);
    5. cache.get(1);       // returns 1
    6. cache.put(3, 3);    // evicts key 2
    7. cache.get(2);       // returns -1 (not found)
    8. cache.put(4, 4);    // evicts key 1
    9. cache.get(1);       // returns -1 (not found)
    10. cache.get(3);       // returns 3
    11. cache.get(4);       // returns 4

    题意

    实现一个LRU缓存机制：查询时，如果不存在目标key，则返回-1，否则返回key对应的value；插入时，如果缓存已满，则将访问时间最远的(key, value)对删去，存入新的(key, value)对。

    思路

    主要思想是维护一个类数组结构，越近访问的数据越靠近头部，越远访问的数据越靠近尾部。每次查询到旧值或访问新值时，将该值从原位置取出并插入到头部；需要删除数据时，只要删去尾部的数据。

    具体实现使用双向链表+HashMap：双向链表使得删除和移动结点的复杂度为146. LRU Cache (M) - 图1；HashMap用于创建索引，将key值映射到对应的结点，使结点查询复杂度也为146. LRU Cache (M) - 图2。

    代码实现

    1. class LRUCache {
    2.     // 双向链表结点
    3.     class Node {
    4.         int key, val;
    5.         Node prev, next;
    7.         public Node(int key, int val) {
    8.             this.key = key;
    9.             this.val = val;
    10.         }
    11.     }
    13.     private Node head, tail;
    14.     private int capacity;
    15.     private Map<Integer, Node> hash;
    17.     public LRUCache(int capacity) {
    18.         this.capacity = capacity;
    19.         hash = new HashMap<>();
    20.         // dummy结点可以大大简化步骤
    21.         head = new Node(-1, -1);
    22.         tail = new Node(-1, -1);
    23.         head.next = tail;
    24.     }
    26.     public int get(int key) {
    27.         if (!hash.containsKey(key)) {
    28.             return -1;
    29.         }
    31.         // 查询到存在，则将原结点拎出插入到头结点之后
    32.         Node target = hash.get(key);
    33.         removeFromPos(target);
    34.         moveToFirst(target);
    35.         return target.val;
    36.     }
    38.     public void put(int key, int value) {
    39.         if (!hash.containsKey(key)) {
    40.             // 需要插入新值，则新建结点并将其移动到头结点后
    41.             Node temp = new Node(key, value);
    42.             hash.put(key, temp);
    43.             moveToFirst(temp);
    44.         } else {
    45.             // 更新旧值，并将原结点取出插入到头结点之后
    46.             Node target = hash.get(key);
    47.             target.val = value;
    48.             removeFromPos(target);
    49.             moveToFirst(target);
    50.         }
    52.         // 超出容量，则删去尾结点之前的结点
    53.         if (hash.size() == capacity + 1) {
    54.             hash.remove(tail.prev.key);
    55.             removeFromPos(tail.prev);
    56.         }
    57.     }
    59.     // 将目标结点移动到头结点之后
    60.     private void moveToFirst(Node target) {
    61.         target.next = head.next;
    62.         head.next.prev = target;
    63.         target.prev = head;
    64.         head.next = target;
    65.     }
    67.     // 将目标结点从链中取出
    68.     private void removeFromPos(Node target) {
    69.         target.prev.next = target.next;
    70.         target.next.prev = target.prev;
    71.         target.next = null;
    72.         target.prev = null;
    73.     }
    74. }