Lru实现一般使用双向链表,hash是辅助快速查找位置
数据的存取主要是通过Hash的,双向链表主要是为了表明哪些个元素应该移除出Hash 和保留。
- Hash + 双向链表队列
Add时检查hash 是否存在O(1),不存在则添加hash,添加list。存在则找到list头结点,更新list和hash为新结点。
Del直接删除hash和list
Get时更新
lru-2算法
- Fifo临时队列
- Hash + 双向链表队列
新访问数据加入fifo,再次访问加入lru队列头部,在lru再次访问,移动到lru头部,
...