LRU淘汰算法

public class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public Integer get(Integer key) {
        if (!map.containsValue(key)) return null;
        //将key变为最近使用
        makeRecently(key);
        return map.get(key);
    }

    public void put(Integer key, Integer val) {
        if (map.containsValue(key)) {
            map.put(key, val);
            makeRecently(key); //设为最近常用
            return;
        }

        if (map.size() >= this.capacity) {
            //链表头部即为最久未使用的key
            Integer head = map.keySet().iterator().next();
            map.remove(head); //移除最老的key
        }
        map.put(key, val); //将新的key添加到链表尾部
    }

    private void makeRecently(Integer key) {
        Integer val = map.get(key);
        //删除key，重新插入到队尾
        map.remove(key);
        map.put(key, val);
    }
}