写在前面

从一道Leetcode题目说起 。

首先，来看一下Leetcode里面的一道经典题目：146.LRU缓存机制，题目描述如下:

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构.

实现 LRUCache 类:

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行.

LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据.

分析

要让 LRU 的 put 和 get 方法的时间复杂度为 O(1)，可以总结出 LRU 这个数据结构必要的条件:

1. 显然 LRU 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
2. 要在 LRU 中快速找某个 key 是否已存在并得到对应的 val；
3. 每次访问 LRU 中的某个 key，需要将这个元素变为最近使用的，也就是说 LRU 要支持在任意位置快速插入和删除元素。

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

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样: