LRU Cache

最近最少缓存

题目

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

解析重点

1.我们需要对缓存的数据根据时间排序，所以我们可以使用数组或者链表。当put数据时，我们按顺序存储数据即可，不过缓存空间有
大小，这时如果空间满了，需要删除第一条数据。当get数据时，可以看作把数据重新put了一次，这时需要把数据重原位置移除，put
到最后。综上，我们使用链表更合适。
2.我们需要以O(1)的时间get和put，所以我们需要同时维护一组hash表。

java代码

因为java里面有了LinkedHashMap，所以我们这里直接使用了。

class LRUCache {
    private Map<Integer, Integer> map;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 注意，需要开启 ordering mode，此时若元素被访问（put、get）就会被移到链表尾
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            /**
             * removeEldestEntry 方法会在插入元素之后调用，用以判断是否需要移除链表表头元素（最近最少访问元素）
             */
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}