LRU是什么意思

LRU是操作系统底层的一个页面置换算法，当空间不够需要换出最长时间没有使用的页面，在本题中的意思就是当到达容量上限的时候要换出最长时间没有被访问过的节点。

如何实现

LRU的实现可以使用链表的方式，参照MySQL的实现，将热数据每次都放到链表头，删除链表尾的冷数据。

题目需要get()和put()方法都是O(1)的事件复杂度，但是链表遍历需要O(n)的时间复杂度，无法满足题目要求，可以想到数组下标索引或者HashMap辅助我们访问，本题如果用数组还需要多写一步hash()来确认key存放的位置，所以我们使用HashMap。

通过HashMap我们可以快速找到节点，也就满足了get()的O(1)，但是对于put()的O(1)，考虑到我们需要删除节点，单链表显然无法满足，因为单链表需要O(n)找到前驱节点，所以我们修改为双链表。

最终的结构就是HashMap + 双链表。

好文链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。