LRU和LFU的实现及优缺点

计算机内部有很多使用缓存的地方，缓存能够保证系统的快速运转。但是一个缓存组件是否好用，取决于它的缓存命中率，而命中率又和缓存组件自己的缓存数据淘汰算法息息相关。常用的缓存算法有：FIFO、LRU、LFU。

FIFO

先进先出算法FIFO(First In First Out)的基本思想是：选择最早调入内存的页面淘汰。
类似于队列的思想，所以实现起来也不困难。

我们通过一个操作系统内的页面置换算法例子来说明一下吧：

这里会导致Belady现象：如果FIFO算法将页面容量增大，缺页率反而升高。

原因如下：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。

LRU

基本原理和场景应用

最近最少使用算法(Least recently used)在vue前端框架的keep-alive内置组件中使用。

我们在使用vue框架使用组件切换，将页面切换前的状态保留在内存中，使用就是LRU算法。

这样做的好处就是：防止浏览器做重复的工作再次渲染页面，从而减少了加载的时间以及减少了计算机的性能消耗，提高了用户的体验。

一个应用场景在计算机底层——页面置换算法，我们现在应用都是从底层算法设计启发而来。比如Java中有一个LinkedHashMap数据结构的实现原理就是使用LRU算法实现的。此数据结构的实现是通过双向链表和哈希表实现的，具体的可以去看LinkedHashMap源码(面试八股文之一)。

举个关于页面置换算法的例子：

更加形象的解释如下：

LRU 算法的常见实现：

• 通常使用链表或者栈的数据结构来实现。

• 当一个数据被访问时，将其移动到链表或栈的顶部，表示它是最近被使用的。

• 这样，在需要淘汰数据时，只需要从链表或栈的底部移除即可。

• 例如，在一些数据库缓存系统中，就采用了基于链表的 LRU 实现方式，通过高效的节点移动操作来保持数据的访问顺序。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "One");
        lruCache.put(2, "Two");
        lruCache.put(3, "Three");

        System.out.println("LRU Cache: " + lruCache);

        lruCache.get(1);  // Accessing 1 to make it the most recently used

        lruCache.put(4, "Four");  // Adding a new entry, which should trigger LRU eviction

        System.out.println("LRU Cache after eviction: " + lruCache);
    }
}

 LFU

LFU算法的基本原理

最不频繁使用算法LFU(Least Frequently Used)在执行淘汰元素的时候，会把最不频繁使用的元素直接删掉，若存在队列中两个元素使用频率相同且最低，那就使用最近使用的时间对元素进行排序，很久没有使用直接删掉此元素。
借用Leetcode上面的题解一张图，这张图可以形象的介绍LFU算法的原理：

LFU 算法的常见实现：

• 一般需要维护一个计数器来记录每个数据的访问次数。

• 当数据被访问时，对应的计数器就会增加。

• 在淘汰数据时，选择访问次数最少的那些数据进行清理。

• 一些缓存框架会使用复杂的数据结构，如带有计数器的哈希表，来实现 LFU 算法，以便快速地查找和更新访问次数。

import java.util.LinkedHashMap;
import java.util.Map;

public class LFUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    private final Map<K, Integer> frequency;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
        this.frequency = new HashMap<>();
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        int currentFreq = frequency.getOrDefault(key, 0);
        frequency.put(key, currentFreq + 1);
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (capacity <= 0) return;
        if (cache.size() >= capacity) {
            evictLFU();
        }
        cache.put(key, value);
        frequency.put(key, 1);
    }

    private void evictLFU() {
        K keyToRemove = null;
        int minFreq = Integer.MAX_VALUE;
        for (Map.Entry<K, Integer> entry : frequency.entrySet()) {
            if (entry.getValue() < minFreq) {
                keyToRemove = entry.getKey();
                minFreq = entry.getValue();
            }
        }
        if (keyToRemove != null) {
            cache.remove(keyToRemove);
            frequency.remove(keyToRemove);
        }
    }

    public static void main(String[] args) {
        LFUCache<Integer, String> lfuCache = new LFUCache<>(3);
        lfuCache.put(1, "One");
        lfuCache.put(2, "Two");
        lfuCache.put(3, "Three");

        System.out.println("LFU Cache: " + lfuCache.cache);

        lfuCache.get(1);  // Accessing 1 to increase its frequency
        lfuCache.get(2);  // Accessing 2 to increase its frequency

        lfuCache.put(4, "Four");  // Adding a new entry, which should trigger LFU eviction

        System.out.println("LFU Cache after eviction: " + lfuCache.cache);
    }
}

 优缺点对比

1. LRU 算法的优点：

   • 实现相对简单，只需要维护一个数据的访问时间顺序即可。

   • 对于突然的访问模式变化能够快速适应，因为它只关注最近的访问情况。

   • 在一些需要快速响应的系统中，LRU 算法能够迅速调整缓存内容，以满足用户的最新需求。

2. LRU 算法的缺点：

   • 可能会受到数据访问的周期性影响。例如，如果一个数据在一段时间内没有被访问，但实际上它在未来可能会再次被频繁使用，LRU 算法可能会因为它的“最近未使用”状态而将其淘汰，导致缓存命中率降低。

   • 对于一些偶尔被访问一次但具有长期价值的数据，LRU 算法也可能会错误地将其淘汰。

3. LFU 算法的优点：

   • 能够更准确地反映数据的长期访问模式，对于那些访问频率稳定的应用场景非常适用。

   • 可以更好地保留那些真正具有高价值的、经常被访问的数据，提高缓存的命中率。

   • 在一些数据访问模式相对固定的系统中，LFU 算法能够提供更稳定的缓存性能。

4. LFU 算法的缺点：

   • 实现相对复杂，需要额外的空间来存储数据的访问次数等信息。

   • 对于访问频率突然变化的情况反应较慢。例如，如果一个冷门数据突然变得热门，LFU 算法可能需要一段时间才能根据其增加的访问次数将其保留在缓存中，在此期间可能会导致用户体验下降。

   • 可能会受到数据访问的初始阶段影响。一个新的数据在开始时访问次数较少，可能会被 LFU 算法过早地淘汰，即使它在未来可能会变得非常重要。

综上所述，LRU 算法和 LFU 算法在缓存淘汰策略中各有优劣，我们需要根据具体的应用场景和需求来选择合适的算法。在实际应用中，也可以根据情况对这两种算法进行适当的优化和调整，或者结合使用，以达到最佳的缓存管理效果。