当前位置:   article > 正文

LFU (最不经常使用算法)缓存

最不经常使用算法

目标

LFU 算法是通过存储每个缓存使用的频率,在缓存容量满了之后,删除使用频率最少的缓存来给新的缓存留出空间。

如果多个缓存节点都拥有最少使用频率,则删除最久未使用的节点。

思路

HashMap 以及LinkedHashSet(链表)。

链表中的 Node 需要存储 key, value, frequency。使用一个 HashMap (frequencyTable)存储键值 frequency -> 链表, 另一个 HashMap(cacheTable)存储键值 key -> Node。

定义一个 minFrequency 记录最少使用的频率。

具体操作

对于 get 操作,我们首先使用 key 来获取 cacheTable 中对应的 node:

1, 如果 key 不存在,则直接返回 null。

2, 如果 key 存在,我们直接从 node 所在的链表中移除该节点,从 node 中获取当前的 frequency 值并加1, 把该 node 插入到 frequency+1 对应的链表尾部,判断是否需要更新minFrequency。

对于 put 操作,我们首先使用 key 来获取 cacheTable 中对应的 node:

1. 如果 key 不存在, 如果没有的话,相当于是新加入的缓存,如果缓存已经到达容量,通过 minFrequency 找到并删除最近最少使用的缓存,再进行插入。

2. 如果 key 存在,其实操作等价于 get(key) 操作,唯一的区别就是我们需要将当前的缓存里的值更新为 value。

实现

如果需要线程安全,只需在 get 和 put方法加上 synchronized 修饰符。

  1. import java.util.HashMap;
  2. import java.util.LinkedHashSet;
  3. import java.util.Map;
  4. public class LFUCache<K, V> {
  5. class CacheNode {
  6. K key;
  7. V value;
  8. int frequency;
  9. CacheNode(K key, V value, int frequency) {
  10. this.key = key;
  11. this.value = value;
  12. this.frequency = frequency;
  13. }
  14. }
  15. private Map<Integer, LinkedHashSet<CacheNode>> frequencyTable = new HashMap<>();
  16. private Map<K, CacheNode> cacheTable = new HashMap<>();
  17. private int minFrequency;
  18. private int capacity;
  19. public LFUCache(int capacity) {
  20. this.capacity = capacity;
  21. this.minFrequency = 0;
  22. }
  23. public void put(K key, V value) {
  24. if (capacity <= 0) {
  25. return;
  26. }
  27. CacheNode node = cacheTable.get(key);
  28. if (node != null) {
  29. node.value = value;
  30. increaseFrequency(node);
  31. } else {
  32. if (cacheTable.size() == capacity) {
  33. removeMinFrequencyNode();
  34. }
  35. addNewCacheNode(key, value);
  36. }
  37. }
  38. public V get(K key) {
  39. if (capacity <= 0) {
  40. return null;
  41. }
  42. CacheNode node = cacheTable.get(key);
  43. if (node != null) {
  44. increaseFrequency(node);
  45. return node.value;
  46. }
  47. return null;
  48. }
  49. private void addNewCacheNode(K key, V value) {
  50. CacheNode newCacheNode = new CacheNode(key, value, 1);
  51. LinkedHashSet<CacheNode> set = frequencyTable.computeIfAbsent(1, k -> new LinkedHashSet<>());
  52. set.add(newCacheNode);
  53. cacheTable.put(key, newCacheNode);
  54. minFrequency = 1;
  55. }
  56. private void removeMinFrequencyNode() {
  57. LinkedHashSet<CacheNode> minFrequencySet = frequencyTable.get(minFrequency);
  58. CacheNode minFrequencyNode = minFrequencySet.iterator().next();
  59. cacheTable.remove(minFrequencyNode.key);
  60. minFrequencySet.remove(minFrequencyNode);
  61. if (minFrequencySet.size() == 0) {
  62. frequencyTable.remove(minFrequency);
  63. }
  64. }
  65. private void increaseFrequency(CacheNode node) {
  66. int of = node.frequency;
  67. LinkedHashSet<CacheNode> set = frequencyTable.get(node.frequency);
  68. set.remove(node);
  69. if (set.isEmpty()) {
  70. frequencyTable.remove(of);
  71. if (of == minFrequency) {
  72. minFrequency++;
  73. }
  74. }
  75. int nf = node.frequency + 1;
  76. node.frequency++;
  77. LinkedHashSet<CacheNode> newSet = frequencyTable.computeIfAbsent(nf, k -> new LinkedHashSet<>());
  78. newSet.add(node);
  79. }
  80. }

 

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号