LRU算法 about basic-programming-knowledge HOT 3 CLOSED

LRU缓存

1. 每次被使用时，数据成为最新的数据
2. 容量满了时，淘汰最久未被使用的数据
3. 新增的数据为最新
4. 每次被get到的数据也是最新

我们先考究一下操作

1. Constructor(capacity)。构造函数，允许设置缓存容量。
2. put(key, value)。放入数据，若存在，则更新value值
3. get(key)。获取数据

如果我们维护一个数组。则涉及到数组的几个操作

1. 查找。get或者put时，要根据key值查找到对应的value，数组的查找O(n)
2. 删除。如果容量满了，会有删除操作O(n)

所以单纯的用数组也不行。那我用一个额外的空间缓存数据呢(空间换时间)？

用一个map来记录每个key对应数组的index

那么每次put和get的时候也更新一下map。
这个方法挺不错的，查找的时间效率可以降为O(1)。但是删除还是那么慢O(n)，因为数组的特性，这里就要考虑换一下数据结构了。

链表的查找为O(n) 删除为O(1)
因为上面我们讲了，如果用一个map来存当前操作到的一些状态，那么可以把查询的时间降低，那么这个方法是否也适用于链表呢？

是的

比如我们在map中已经有(key, node)。在put的时候，就可以快速定位到一个node。因此这里我们的map需要存node信息。
但是又有另外一个麻烦。

单链表删除，已知链表和node，还是得遍历一次链表

因此，我们需要用双链表，因为双链表中的node保存了前后信息，删除时不需要遍历整个链表，真正的又快又好。

至此，我们利用一个map存储每个活动节点，把遍历操作改为了查map的操作，同时，由于map内存储的节点是双向指针，那么不管是增加和删除，时间复杂度都是O(1)

而对于map而言，set、has、get操作都是O(1)，因此整体结果

• 时间复杂度 O(1) -> get、put
• 空间复杂度 O(n) -> get、put

from basic-programming-knowledge.

厉害了，大佬

from basic-programming-knowledge.

leetcode 460

from basic-programming-knowledge.