在正式设计热点数据服务之前，我们先了解几个知识点

1、FIFO，LRU和LFU

FIFO

核心思想：如果最早进入缓存的数据在最近没有被访问，那么在未来它被访问的可能性也很小。因此，当缓存满了之后，最早进入缓存的数据最先被淘汰

在FIFO算法中，缓存被看作是一个队列；新数据首先进入队列的尾部，当需要替换数据时，从队列的头部开始查找并替换

缺点：

1、Belady现象：因为当新的数据库进入缓存时，可能会替换掉那些即将被访问的数据块

2、FIFO算法不考虑数据的访问模式或频率，因此可能会导致频繁访问的数据块被频繁地替换出缓存

LRU

基本思想：如果一个数据在最近一段时间内没有被访问到，那么在未来它被访问的可能性也很小。因此，当缓存空间不足时，最久未使用的数据最先被淘汰

LRU算法实现：双向链表+哈希表

双向链表记录缓存中数据的访问顺序，最近访问的数据放在链表头部，最久访问的数据放在链表尾部

哈希表建立数据到链表节点的映射，以便在O(1)的时间复杂度内完成数据的查找和删除操作

访问过程：

当访问一个已经存在于缓存中的数据时，需要将其移到链表头部，表示最近被访问过；

当访问一个不存在于缓存中的数据时，需要先在哈希表中查找该数据是否已存在；如果存在，则将其移到链表头部；如果不存在，则需要从链表尾部淘汰一个数据，并将新数据插入到链表头部

缺点：

1、LRU可能会导致抖动现象，既频繁地淘汰和重新加载同一组数据；

2、在数据开始被频繁访问之前，其访问频率较低，导致被错误地淘汰；

LFU

核心思想：最近最少使用，如果一个数据在最近一段时间内被访问的次数很少，那么在未来它被访问的可能性也很小当缓存空间不足时，LFU算法会选择访问次数最少的数据进行淘汰

LFU算法的实现：计数器数组+哈希表

计数器数组用来记录每个数据被访问的次数，哈希表用来建立数据到计数器数