LRU就是一种缓存淘汰策略。 计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？ LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。  LRU 算法设计 分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件： 显然 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。 我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val； 每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。 那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。 LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。 如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。 对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。(结点设计是同时存入key和value) 链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。必须是双向链表，有前向信息才能在任意位置删除结点。 put 方法它的逻辑：  * **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/