题目：

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.
Follow up:
Could you do both operations in O(1) time complexity?

Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

题目大意

这是一个经典的题目，设计一个LRUCache。LRU 是一个缓存算法， 在实际编程中使用的很广泛，比如页面置换算法和图片缓存。

思路

思路其实就是理解LRU这个算法，然后按照思路去实现就好。

Java其实已经实现了这个算法，重写LinkedHashMap的removeEldestEntry方法，给定删除元素的触发条件即可。至于LinkedHashMap内部是如何实现的这里不再赘述，有兴趣的可以去看看源码。这里我使用了另外一种实现方式，HashMap加双向链表。

对外的API主要有两个，put和get，其实应该还有一个clear方法，用于清空整个缓存，这个方法实现较为简单，只需要把双向链表首尾置空，然后初始化HashMap即可。

其实LRUCache里还有两个很重要的内部方法moveToFirst和trimToSize，moveToFirst主要完成将元素放到队首的操作，trimToSize则将缓存数量恢复到额定大小。

get

按照LRU的原理，每次执行get方法先检查缓存里是否存在，不存在则直接返回空，存在则将该元素放到双向链表的队首并返回。

如果没有HashMap的话，检查缓存是否存在是一个比较消耗时间的操作，需要从队首开始遍历一直到队尾，用HashMap能加速访问。

put

put方法比较复杂，要做的操作很多。

首先检查缓存里是否存在，如果存在则更新value值将其放到队首；如果不存在则新建一个key-value对象，将这个新建的对象放到HashMap和双向链表的队首，之后还需要检查当前数据数量是否超过缓存大小，如果超过了则需要去除队尾的数据。

代码实现

这里按照Leetcode上的要求完成，key和value都是Integer类型，但实际使用编写的时候最好使用泛型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class LRUCache {
    private HashMap<Integer, Node> map;
    private int capacity = 0;
    private int size = 0;
    Node head, tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }
    
    public int get(int key) {
        Node tmp = map.get(key);
        if(tmp == null) {
            // 该元素不存在
            return -1;
        } else {
            // 该元素存在，放到队首并返回
            addToHead(key);
            return tmp.val;
        }
    }
    
    public void put(int key, int value) {
        Node tmp = map.get(key);
        if(tmp == null) {
            // 元素不存在，新建键值对，并更新缓存数量
            tmp = new Node(key, value);
            map.put(key, tmp);
            size ++;
        } else {
            tmp.val = value;
        }
        // 无论元素是否存在，都需要将其放到队首
        addToHead(key);
        
        // 检查缓存数量是否超过容量
        if(size > capacity) {
            trimToSize();
        }
    }
    
    // 将元素放入队首操作，情况较多
    private void addToHead(int key) {
        Node tmp = map.get(key);
        // 元素本来就在队首
        if(tmp == head) {
            return;
        }
        // 元素在队尾，更新队尾指针
        if (tmp == tail) {
            tail = tail.pre;
        }
        // 重新建立双向链接
        if(tmp.pre != null) {
            tmp.pre.next = tmp.next;
        }
        if(tmp.next != null) {
            tmp.next.pre = tmp.pre;
        }
        // 放队首操作
        tmp.pre = null;
        tmp.next = head;
        if(head != null) {
            head.pre = tmp;
        }
        head = tmp;
        
        // 特殊情况，第一次添加数据，需要更新队尾
        if(tail == null) {
            tail = tmp;
        }
    }
    
    private void trimToSize() {
        // 删除队尾数据
        size --;
        map.remove(tail.key);
        tail = tail.pre;
        tail.next = null;
    }
    
    class Node{
        // 数据实体
        int val = 0;
        int key = 0;
        Node next;
        Node pre;
        public Node(int key, int val) {
            this.val = val;
            this.key = key;
            next = null;
            pre = null;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Leetcode运行时间不稳定，一样的代码两次提交运行时间一样，这里放一张时间更短的。

运行时间
运行时间