LRU就是一种缓存淘汰策略。 计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢? LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。 ![](https://img.kancloud.cn/b9/7c/b97cceb16fe4b1de031ce0e0a19a9efe_670x429.png) LRU 算法设计 分析上面的操作过程,要让 put 和 get 方法的时间复杂度为 O(1),我们可以总结出 cache 这个数据结构必要的条件: 显然 cache 中的元素必须有时序,以区分最近使用的和久未使用的数据,当容量满了之后要删除最久未使用的那个元素腾位置。 我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val; 每次访问 cache 中的某个 key,需要将这个元素变为最近使用的,也就是说 cache 要支持在任意位置快速插入和删除元素。 那么,什么数据结构同时符合上述条件呢?哈希表查找快,但是数据无固定顺序;链表有顺序之分,插入删除快,但是查找慢。所以结合一下,形成一种新的数据结构:哈希链表 LinkedHashMap。 LRU 缓存算法的核心数据结构就是哈希链表,双向链表和哈希表的结合体。 如果我们每次默认从链表尾部添加元素,那么显然越靠尾部的元素就是最近使用的,越靠头部的元素就是最久未使用的。 对于某一个 key,我们可以通过哈希表快速定位到链表中的节点,从而取得对应 val。(结点设计是同时存入key和value) 链表显然是支持在任意位置快速插入和删除的,改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素,而这里借助哈希表,可以通过 key 快速映射到任意一个链表节点,然后进行插入和删除。必须是双向链表,有前向信息才能在任意位置删除结点。 put 方法它的逻辑: ![](https://img.kancloud.cn/85/e9/85e9c5d259620b071e8f6d2de9feccc2_792x626.png) * **LRU缓存机制的核心:双向链表(保证元素有序,且能快速的插入和删除)+hash表(可以快速查询)** * **为什么使用双向链表**?因为:对于删除操作,使用双向链表,我们可以在O(1)的时间复杂度下,找到被删除节点的前节点。 * **为什么要在链表中同时存键值,而不是只存值?** 因为:当缓存容量满了之后,我们不仅要在双向链表中删除最后一个节点(即最久没有使用的节点),还要把cache中映射到该节点的key删除,这个key只能有Node得到(即hash表不能通过值得到键)。 leetcode LRU算法题:https://leetcode-cn.com/problems/OrIXps/ 题解:https://leetcode-cn.com/problems/OrIXps/solution/tong-guan-jian-2-mei-you-pai-ming-shou-d-buuu/