参考资料1
参考资料2
参考资料3
一：FIFO
FIFO：先进先出;原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。
思想：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。
实现：双向链表(LinkedList)保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。
二：LFU :
LFU :Least Frequently Used最近使用频率最少算法；注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
思想：当缓存满的时候，应当把访问频次最少的数据给淘汰掉。
实现：利用一个数组存储数据项，用HashMap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。
在插入数据(插到数组的尾端)和访问数据(数组随机访问)的时候都能达到O(1)的时间复杂度；
淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
网友评论