Redis-淘汰算法

Count->2

Count-4

Node4

最少使用，也就是淘汰缓存中访问频率最低的记录。LFU 认为，如果数据过去被访问多次，那么将来被访问的频率也更高。LFU 的实现需要维护一个按照访问次数排序的队列，每次访问，访问次数加1，队列重新排序，淘汰时选择访问次数最少的即可。LFU 算法的命中率是比较高的，但缺点也非常明显，维护每个记录的访问次数，对内存的消耗是很高的；另外，如果数据的访问模式发生变化，LFU 需要较长的时间去适应，也就是说 LFU 算法受历史数据的影响比较大。例如某个数据历史上访问次数奇高，但在某个时间点之后几乎不再被访问，但因为历史访问次数过高，而迟迟不能被淘汰。

KEY5

节点地址

Node5

LRU(Least Recently Used)

Count->1

1. 字典（map）存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1)，在字典中插入一条记录的复杂度也是O(1)。2. 双向链表(double linked list)实现的队列。将所有的值放到双向链表中，这样，当访问到某个值时，将其移动到队尾的复杂度是O(1)，在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

KEY1

LFU(Least Frequently Used)

链表地址

KEY4

Head

KEY3

End

Node1

map

双向链表

Node2

KEY2

Count-3

Node3

1.每个元素以双向链表的形式关联保存2.每条链保存的元素访问次数都相同3.当内存满后需要淘汰，淘汰访问次数最少的

字典（Map）key：保存 元素KEY的哈希值，value：对应元素的节点内存地址

Count-5

保存访问次数 （也可通过hash表实现）Key：当前访问次数Value：双向链表地址