题解 | #设计LRU缓存结构#

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    private final LinkedHashMap<Integer, Integer> cache;

    public Solution(int capacity) {

        this.cache = new LinkedHashMap((int) (capacity / 0.75f + 2), 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return this.size() > capacity;
            }
        };

    }

    public int get(int key) {
        Integer v = cache.get(key);

        return v == null ? -1 : v;
    }

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

熟悉常用工具类LinkedHashMap的情况下，此题用java解题，应该是最方便的。

需要注意的细节如下：

①容量已知，因此创建LinkedHashMap实例的时候，就可以足量分配，避免容量扩展和重新hash。

②由于题目要求按照访问顺序排列缓存，因此需要设置LinkedHashMap的accessOrder布尔变量为true。

③题目要求容量满则淘汰最久未使用的条目，因此需要覆写removeEldestEntry方法。此方法会在put方法插入完成的末尾调用，方法的具体作用名称已经体现——移除最老的条目。

（ps：阅读第三方缓存工具类的源码的时候，可以看到LinkedHashMap的更具体的使用方法。jdk8官方教程集合部分，也有说到LinkedHashMap的removeEldestEntry方法的用途。）