Lru实现一般使用双向链表,hash是辅助快速查找位置

数据的存取主要是通过Hash的,双向链表主要是为了表明哪些个元素应该移除出Hash 和保留。

  1. Hash + 双向链表队列

​ Add时检查hash 是否存在O(1),不存在则添加hash,添加list。存在则找到list头结点,更新list和hash为新结点。

​ Del直接删除hash和list

​ Get时更新

lru-2算法

  1. Fifo临时队列
  2. Hash + 双向链表队列

新访问数据加入fifo,再次访问加入lru队列头部,在lru再次访问,移动到lru头部,

参考

https://cloud.tencent.com/developer/article/1664672