1、 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置

2、需要在 cache 中快速找某个 key 是否已存在并得到对应的 val

3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的， cache 要支持在任意位置快速插入和删除元素

什么数据结构同时符合上述条件？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap

LRU 缓存算法的核心数据结构是哈希链表，双向链表和哈希表的结合

1、每次默认从链表尾部添加元素，越靠尾部的元素就是越近使用的

2、对于某 key 可以通过哈希表快速定位到链表中的结点从而取得对应 val

3、因为需要删除操作，删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)

由于要同时维护双向链表和哈希表，容易漏掉一些操作，比如删除某 key 时在 cache 中删除对应 Node 却忘记在 map 中删除响应 key。解决这个问题的有效办法是在这两种数据结构上提供一层抽象 API 即尽量让主方法 Get Put 避免直接操作 map cache 可先实现以下函数

// 将某 key 提升至最近使用
private void makeRecently(int key) {
	Node x = map.get(key);
	// 先从链表中删除此节点
	cache.remove(x);
	// 重新插到队尾
	cache.addLast(x);
}
// 添加最近使用的元素
private void addRecently(int key, int val) {
	Node x = new Node(key, val);
	// 链表尾部就是最近使用的元素
	cache.addLast(x);
	// 在 map 中添加 key 的映射
	map.put(key, x);
}
// 删除某 key
private void deleteKey(int key) {
	Node x = map.get(key);
	cache.remove(x);
	map.remove(key);
}
// 删除最久未使用元素
private void removeLeastRecently() {
	// 链表头部-最久未使用
	Node deletedNode = cache.removeFirst();
	// map 中删除
	map.remove(deletedNode.key);
}

Get

public int get(int key) {
    if (!map.containsKey(key)) {
        return -1;
    }
    // 将该数据提升为最近使用的
    makeRecently(key);
    return map.get(key).val;
}

Put

public void put(int key, int val) {
	if (map.containsKey(key)) {
		// 删除旧的数据
		deleteKey(key);
		// 新插入数据为最近使用
		addRecently(key, val);
		return;
	}
	if (cap == cache.size()) {
		// 删除最久未使用
		removeLeastRecently();
	}
	// 添加为最近使用
	addRecently(key, val);
}