如何优雅地实现LRU缓存淘汰算法？

良心公众号

关注不迷路

作为服务端研发而言，缓存是在日常工作中很难绕过的一个话题，也是在面试过程中几乎必考的重点。这一点尤其凸显在对性能有较高要求的项目上，出于各种各样的考虑，比如为了提升接口响应速度，抑或是为了减轻对数据库的压力……我们通常都会对相应的数据作缓存操作，从而提升服务的性能。

其实，缓存不仅广泛应用于服务端研发中，其设计思想在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

如果对缓存的概念给出一个相对书面的阐述，则缓存是一种依赖空间换取时间从而提高数据读取性能的技术。其适用于空间充足，但对时间要求较高的场合。随着硬件相关技术的发展，因为空间不足对系统的带来的限制已经趋弱，而对时间的追求则是永恒的，因此，缓存技术就显得更加重要。

了解了缓存的概念，重要性及其应用场景之后，很容易能够理解，缓存的大小是有限的，它不可能一直不停地对数据加以存储，而不做相应地清理动作。因此，采用不同的清理思路，就催生了不同的缓存淘汰策略。

常用的缓存淘汰策略有：先进先出FIFO、最少使用LFU、最近最少使用LRU。下面对这三种缓存淘汰策略的特点进行大致的描述：

• 先进先出FIFO策略，与队列的特性如出一辙，拿队列来理解，就是当缓存来时添加到队尾，当缓存满时队头出队，谓之淘汰；

• 最少使用LFU策略，则是对缓存的使用情况进行计数，每次当缓存满时，淘汰掉缓存中使用次数最少的数据。

• 对比上述两种策略，可以看出，FIFO策略考虑的是时间上的优先级，而LFU策略考虑的是使用次数上的优先级，而本文将要阐述的重点——最近最少使用LRU策略，则是对时间和使用次数的考虑兼而有之。在更多的情况下，LRU策略更加合理，因为其更能体现数据的近期使用频率，从而使缓存中的数据更加贴近热点数据，以达到更好地提升性能的目的。

接下来，让我们一起来看一下本文的主角：LRU缓存淘汰算法。只要对LRU缓存淘汰策略稍加分析就不难发现，根据其最近最少使用的特点，采用链表这种数据结构去维护缓存数据是非常合适的。至于原因，在接下来的分析和实现过程中，我想你将深有体会。在具体实现LRU缓存算法之前，我们先来梳理一下该算法处理数据的思路，具体可以分为三种情况：

• 待缓存的数据未存在于缓存链表中，且缓存空间未满

• 待缓存的数据未存在于缓存链表中，且缓存空间已满

• 待缓存的数据已存在于缓存链表中

到这里，为什么采用链表这种数据结构实现LRU缓存策略，已经比较明显了。因为对于上述三种情况的缓存更新，与链表的特点实在是太过匹配。我们一一来看，上述三种情况具体对应于链表的哪些操作：

• 待缓存的数据未存在于缓存链表中，且缓存空间未满，此时只需将待缓存数据添加至链表头部（或尾部）即可

• 待缓存的数据未存在于缓存链表中，且缓存空间已满，此时只需将链表尾部（或头部）的数据删除，并将待缓存数据添加至链表头部（或尾部）即可

• 待缓存的数据已存在于缓存链表中，此时只需将待缓存数据从原先的位置删除，并将其插入至链表头部（或尾部）即可

对上述步骤的时间复杂度加以分析，无论缓存是否已满，我们都需要对链表进行遍历，以确定待缓存数据是否已经存在于缓存中，这个过程最好的时间复杂度为O(1)，最坏的时间复杂度为O(n)，平均时间复杂度为O(n)。那么，有没有更好的实现方式，使其时间复杂度逼近常量呢？答案是有的，只需要引入散列表来记录每个缓存数据的位置，即可避免遍历整个链表，这也是典型的空间换时间思想的应用。在该优化中，链表 + 散列表在Java中对应的数据结构便是LinkedHashMap。

分析至此，一切都已经如拨云见日般明晰了，话不多说，Talk is cheap, show me the code!

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


/**
 * 本程序及其注释在JDK11验证通过
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> {


    // 默认负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;


    // 缓存最大容量
    private final int MAX_CACHE_SIZE;


    // 自定义负载因子
    private final float LOAD_FACTOR;


    // 缓存主体LinkedHashMap
    private final LinkedHashMap<K, V> cacheMap;


    public LRUCache(int maxCacheSize, float loadFactor) {
        MAX_CACHE_SIZE = maxCacheSize;
        // 可根据具体情况自定义负载因子
        LOAD_FACTOR = loadFactor;
        // 根据缓存最大容量计算Map的初始化容量，避免扩容影响性能
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / LOAD_FACTOR) + 1;
        // accessOrder设置为true，表示在插入或者访问的时候，都会更新缓存，将该数据插入链表尾部或者移动至链表尾部
        cacheMap = new LinkedHashMap<>(capacity, LOAD_FACTOR, true) {
            private static final long serialVersionUID = 1001L;
            // 重写removeEldestEntry方法，当cacheMap的size超过缓存最大容量时，将链表头部数据移除
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }


    public LRUCache(int maxCacheSize) {
        // 使用默认负载因子
        this(maxCacheSize, DEFAULT_LOAD_FACTOR);
    }


    public void put(K key, V value) {
        cacheMap.put(key, value);
    }


    public V get(K key) {
        return cacheMap.get(key);
    }
}

本文关于LRU缓存淘汰算法的总结及其实现就到这里了。欢迎大家一起讨论技术，共同成长！

学习 | 工作 | 分享

????长按关注“有理想的菜鸡”

只有你想不到，没有你学不到