算法之缓存LFU
LFU(Least Frequently Used)最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小”的思路。
举个例子,缓存空间大小为3:
- put(1,”a”)
- put(2,”b”)
- get(1)
- get(2)
- put(3,”c”)
- put(4,”d”) // 按照LFU应该淘汰{3,”c”}
如何设计
- 缓存需要存储key-value对.
显然,对于key-value对的存储使用map是很高效的。时间复杂度可以达到O(1)级别。
- 假设使用数组存储访问次数:
- 那么插入数据时,复杂度是O(1),次数直接插入数组末尾
- 访问时,复杂度是O(1).
- 淘汰时,复杂度是O(n),遍历淘汰最小值。
- 假设使用有序数组存储访问次数:
- 那么插入数据时,复杂度是O(1),次数直接插入数组末尾
- 访问时,复杂度是O(logn).
- 淘汰时,复杂度是O(1),遍历淘汰最小值。
- 使用两层链表,外层链表的每个节点代表一组拥有同样访问次数的key,每个节点自身也是一个链表,内层链表确保上次访问时间最早的key位于内层链表的尾部。在这一数据结构下,我们在插入key时判断外层链表尾部元素的freq(次数)是否为0,如果是,将key插入该内层链表的头部,如果否,生成一个只包含key的外层链表,插入到外层链表的尾部。在访问key时,将该key移动到外层链表的下一个节点的头部。这样一来,在移除key时,只需要移除外层链表尾部元素的尾部元素即可,插入、访问、移除的时间复杂度都是O(1)。
1 | class Node<K,V> { |
treemap
还有一种使用 jdk treemap 实现 LFU 的方案,treemap 可以实现对key的排序,其底层是一棵树,实现了map接口:
1 | private TreeMap<Wrapper<K extends Comparable >,V> caches = new TreeMap<>(); //有序 |