缓存的本质以空间换时间，那么缓存的容量大小肯定是有限的，所以要定制缓存的淘汰策略
先进先出算法（FIFO）//淘汰一定时期内被访问次数最少的页面（LFU：(Least Frequently Used )根据数据的历史访问频率来淘汰数据，LFU算法中的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序）//淘汰最长时间未被使用的页面（LRU）
LRU设计原则：根据对数据的历史访问次数来进行淘汰数据的，通常使用链表来实现。在缓存中，他的设计原则是：如果数据最近被访问过，那么将来他被访问的几率也很高。
LRU状态
步骤：1. 新加入的数据插入到链表的头部
- 每当缓存命中时（即缓存数据被访问），则将数据移到链表头部
- 当链表已满时，将链表尾部的数据丢弃
LRU的具体实现
利用双向链表和散列表结合：
1.双向链表支持查找前驱，保证操作的时间复杂度o（1）
-
引入散列表记录每个数据的位置，将缓存访问的时间复杂度降到o（1）
image.png
