缓存淘汰算法LRU和LFU( 二 ) 前言LRU算法和LFU算法是属于页面置换的

文章插图
如上，双哈希表需要维护两个哈希表以及一个最少频次使用的计数minFreq 。
第一个哈希表是 freq_table ，它的key是访问的频次，它的value是一个双向链表，双向链表的每一个节点包含三个元素：key ， value ，以及count 。
第二个哈希表是 key_table ，它的key是双向链表中存储的key ， value是对应节点的指针（这样查找的时间复杂度就是O(1)）。
【缓存淘汰算法LRU和LFU】类比LRU ， LFU的步骤如下：

1.假设LFU缓存容量为3 ，且一开始初始化插入三个键值对（1 ， 1），（2 ， 2），（3 ， 3）此时每个键值对的频次都是1 ，所以它们都在同一个双向链表上，如图四。
2.假设这时候查找key=1 ，由于key_table存储的是节点的指针，所以可以以O(1)的复杂度得到结果。
2.1 注意此时节点1的频次由1变为2 ，所以要将节点1移动到频次为2的链表，如图五
2.2 另外， minFreq也要记得同步更新，不过本次操作不用。
3.假设这时候插入一个新的键值对（4 ， 4），由于它的频次为1 ，所以对应链表1 ，它会被插入到链表1的最前面，而由于这种操作，所以同链表的最后一个元素肯定是最晚插入的。
3.1 由于新加的元素导致容量溢出，所以我们要删除频次最少，插入时间最晚的，即图五的（3 ， 3 ， 1）

文章插图