我们知道 redis 很高效，那是别人告诉我们的，至于 redis 为什么那么快，你有没有仔细考虑过。今天我们手写一个 LRU，redis 里常用的一个策略

一、题目描述

146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化LRU缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

二、思路分析

第一想法

• 刚看到本题时没有多想就觉得会用到队列，因为队列 FIFO 可以做到淘汰末尾数据，但是仔细一想本题是需要淘汰最近最少使用数据，如果仅仅是最近的数据那么队列很容易实现。加上使用频率就涉及到数据的频繁挪动。很明显队列是无法完成的。

• 那么有没有一种顺序添加的数据，每次在获取之后就会将数据前移至一端呢？答案是有的！LinkedHashMap
  

• LinkedHashMap 不熟悉的朋友们可以简单的将它理解成HashMap 。 下图展示了HashMap的存储结构

• 上述的元素我这里做了个动画演示全过程！！！

• 而LinkedHashMap只是多了一条链表串起里面的元素

• 这也是为什么LinkedHashMap是按照顺序存储的。但是LinkedHahsMap也无法做到按照使用频率进行排序啊？大家都知道他是按照添加顺序排序的！！！

*LinkedHashMap*改造

• 原生的LinkedHashMap的确无法满足情况，但是我们稍微看下源码能够发现在 put 之后都会执行下afterNodeInsertion 这个方法。这也是HashMap留给LinkedHashMap做的扩展！

• removeNode 就是将最前面的数据。想要进入这个方法就需要removeEldestEntry判断。LinkedHashMap默认是 false . 所以我们只需要重写他就行了。但是还是在 get 值的时候如何保值在最后面呢？我们仔细看下源码就能够发现在get中有这个一个方法afterNodeAccess 。他的作用就是将 get 的元素移位值后面。正好符合我们LRU的策略特征

• 综上！我们借助LinkedHashMap就非常容易的实现了 LRU 策略！

自己实现

• 但是本题的意思是想考察我们自己是如何实现的，而不是巧妙对现有的工具改造的！不过上面对LinkedHashMap的确改造的很巧这是不可否认的！下面我们就尝试自己来实现下这种方式！

• 首先我们需要确定需要用到 Hash 结合链表来实现。Hash 我们自然使用HashMap来存储数据为的就是方便定位数据。定位到数据就需要操作链表将数据实时移位值链表尾部，每次淘汰是将链表首位移除既可。为了方便我们操作链表这里的链表肯定是双链表的！

链表单元

• 首先我们定义一个内部类！用于链表的基本单元。里面存储了 key,value 方便根据 Hash 中存储的内容找到节点！preNode，nextNode分别指向前后节点

• 在构建器中初始化容量和链表大小，并初始化边界节点方便我们操作节点中移位和删除。

• 在获取数据时没有添加就返回-1 ， 已经添加的数据则将该数据对应的 node 节点移动到链表的尾部。

• 在 put 中当第一次添加我们需要维护链表大小并进行检测是否需要进行淘汰数据，如果不是第一次添加我们只需奥更新值和对应 node 在链表中的位置即可

四、总结

• 虽然执行时间和内存消耗有点高！但是我就是不优化。

• 本题主要就是在链表的移动上面会复杂点。我们需要按照添加顺序和使用频率两个维度进行维护他们之间的顺序。只要这个顺序维护好，就没啥问题了！