LFU

LFU，最近不经常使用，把数据加入到链表中，按频次排序，一个数据被访问过，把它的频次+1，发生淘汰的时候，把频次低的淘汰掉。

比如有数据 1，1，1，2，2，3

缓存中有（1(3次)，2(2次)）

当3加入的时候，得把后面的2淘汰，变成（1(3次)，3(1次)）

区别：LRU 是得把 1 淘汰。

LFU对于交替出现的数据，缓存命中不高

比如，1，1，1，2，2，3，4，3，4，3，4，3，4，3，4，3，4......

由于前面被（1(3次)，2(2次)）

3加入把2淘汰，4加入把3淘汰，3加入把4淘汰，然而3，4才是最需要缓存的，1去到了3次，谁也淘汰不了它了。

要求是缓存的加入put()，缓存读取get()，都要在O(1)内实现。

LFU的一个实现方法：

用一个主双向链表记录（访问次数，从链表头），从链表中按时间顺序记录着（key） 用一个哈希表记录（key，(value, 主链表ptr，从链表ptr)）ptr表示该key在链表中的地址 然后，get，put都在哈希表中操作，近似O(1)，哈希表中有个节点在链表中的地址，能O(1)找到，并把节点提搞访问频次，链表插入删除也都是O(1)。