LRU 缓存

LRU是Least Recently Used的缩写，即最近最少使用，是一种替换算法。

cache

内存分三级缓存 L1 D-cache是处理速度最快的，也是容量最小的，如何往里面存数据，就需要用到替换算法。

LRU cache

• 缓存是有限的，在缓存满的时候，删除哪些元素，就有不同的缓存删除策略
• 在缓存满的时候，删除缓存里最久未使用的数据，然后再放入新元素
• 数据的访问时间很重要，访问时间距离现在最近，就最不容易被删除。

get实现：
判断hash 中Key是否存在，不存在返回-1 ； 存在则返回对应的值，并把节点添加到头部
put实现：
判断hash 中Key是否存在，不存在：1.添加新的节点到头部，添加到哈希，并size++，检查容量大小，容量大于cap时，删除尾部节点，删除哈希key，size—；

存在则更新的值，并把节点添加到头部。
get put 操作时，只有
添加到头部
|—-删除节点 （最小操作）
移动到头部—
|—-添加到头部（最小操作） 全部都可以由这两个基本操作完成

删除尾部 —删除尾节点， 返回删除节点。