我们需要实现这样的一个cache(key-value pair):

  • 取数据时，存在则取出，不存在则返回-1
  • 存数据时，若该key已存在，则更新其value。若不存在，则插入之。插入时，若cache已满，则需要先删除一个元素。删除时，使用LFU算法，将使用频率最低的元素删除；若有多个使用频率相同的元素，则对这些元素采用LRU算法，删除最久未使用的。

很显然，我们需要用map来存储key-value pair。然后记录各个元素的使用频率，以及最近访问的次序。主要有下面三个操作：

  1. 获取数据：从cache中获取指定Key对应的元素，同时更新使用频率以及最近访问的次序。
  2. 插入数据：将新元素插入到cache
  3. 删除元素：当cache已满时，按照LFU-LRU算法删除一个元素

只记录频率

若只考虑记录使用频率，我们可以使用最小堆来实现：

使用两个map，一个存key-value pair，记为map1;一个存key-node pair,记为map2。node中存频率。

  • 获取数据：从map1取出数据用来返回，从map2取出node，将频率增加之后，调整以其为根的子树，使其满足最小堆的性质。
  • 插入数据：将数据存到map1，生成一个新node,频率为0，将其插入最小堆。
  • 删除数据：先从map1中删除堆顶元素对应的数据，然后从删除堆顶元素，并调整结构即可。

只记录最近访问顺序

同样需要两个map,只是此时的node是双向链表中的node。维护一个双向链表，记录首尾指针

  • 获取数据：从map1中获取数据；然后将双向链表中对应的node移到链表最前面。由于是双向链表，整个过程只需要更改左右指针即可。
  • 插入数据：插入数据到map1；将新生成的node放置到链表最前面
  • 删除数据：从map1中删除链表末尾的node对应的数据；然后将该node从链表中删除。

结合频率与访问顺序

可以发现，使用堆来记录访问频率时，上述三个操作中，每个操作的算法复杂度都是O(logn)；而用双向链表记录访问次序时，每个操作的算法复杂度都是O(1)。

从堆中找到频率最小者后，还需要从双向链表中找出对应频率的node，才能根据其在链表中的相对次序移除最近未使用者。计算相对次序时，无异于遍历整个链表了，本来O(1)的算法会降为O(n)了。怎么将二者结合起来呢？

既然每个频率都要找出一个相对而言的LRU List，我们为何不弃用最小堆，直接记录频率与LRU List的关系呢？

如图所示，将频率依次用双向链表连接，每个频率都有一个对应的LRU List与之关联。我们仍要维护两个map。map1存储key-node pair,node都要记录其对应的值以及频率;map2存frequency-node,此node要记录其对应的LRU List

  • 获取数据：从map1中获取数据node.value，此时，node的频率要增加，因此要通过map2[node.freq+1]找到对应的频率LRU List。如果不存在，则创建LRU List。存在则将node放到队首。
  • 插入数据：先找到频率链的队首，若队首频率为0，则将新建的node加入LRU List的队首，否则要新建一个频率为0的。
  • 删除数据：删除频率链队首对应的LRU List队尾元素

三种操作算法复杂度都是O(1)。

Reference: An O(1) algorithm for implementing the LFU cache eviction scheme

Code: https://github.com/YieldNull/leetcode/blob/master/460_LFU_Cache.java