简单的LRU本地缓存实现-Java版本

在这里插入图片描述

文章目录

什么是缓存
- 缓存的种类
- 缓存的关键特性
- 缓存的优势与挑战
- - 优势：
  - 挑战：
- 缓存的应用场景
- 什么是LRUCache
- LRU 缓存的工作原理
- 核心操作
- 为何选择 LRU
- 使用场景
一个简单的LRU缓存实现
相关资料
- 基础资料

什么是缓存

缓存（Cache）是一种高速数据存储层，它可以存储临时数据副本，让未来的请求能够更快地访问这些数据。缓存存在的主要目的是提高数据访问速度和提升系统的整体性能。缓存中的数据通常来源于原始数据的一个子集，这些原始数据可能存储在一个较慢的存储系统中，比如硬盘驱动器或远程数据库。

缓存的种类

硬件与软件缓存：

硬件缓存：CPU缓存是一种高速存储器，能够暂存从主存储器（RAM）中读取的数据，从而加快数据访问速度。
软件缓存：在软件开发中，可以实现多种类型的缓存策略来存储经常访问的数据或结果，如Web页面缓存、数据库缓存等。

客户端缓存和服务器端缓存：

客户端缓存，如Web浏览器缓存，存储静态页面，以减少数据的重复下载。
服务器端缓存，如数据库查询缓存，存储常见查询结果或计算结果，以减少数据库访问次数和计算负担。

分布式缓存：
分布式缓存系统，如Redis和Memcached，提供了一个由多台服务器组成的缓存池，可以大幅提高缓存容量和处理能力。

缓存的关键特性

数据一致性：缓存数据与源数据在更新时需要保持一致，否则可能会出现数据过时的问题。
缓存淘汰策略：当缓存容量不足时，需要通过一定的策略删除部分缓存数据，常见策略有最近最少使用（LRU）、最不经常使用（LFU）等。

缓存的优势与挑战

优势：

减少了对原始数据源（如数据库）的访问次数，降低了系统的整体负载。
减少了数据访问的延迟，提供了更快的响应时间。
提高了资源的利用效率，可以通过缓存复用之前的计算结果。

挑战：

缓存与数据源之间的一致性管理。
缓存数据的过期策略和淘汰策略。
分布式缓存中的数据分片和同步问题。

缓存的应用场景

Web应用：缓存静态页面、图片、JavaScript文件等，减少服务器的计算和带宽消耗。
数据库系统：缓存频繁执行的查询结果，减少数据库的查询次数。
大数据处理：缓存中间结果，加快大数据计算和分析过程。

总的来说，缓存是提升系统性能、加快数据访问速度的关键技术之一。合理地设计和使用缓存可以极大提升应用程序的性能和用户体验。然而，也需要小心处理缓存带来的数据一致性和管理挑战。

什么是LRUCache

最近最少使用（LRU）缓存是一种常见的缓存策略，用以管理在有限的缓存空间中存储的数据。LRU 缓存的核心思想是当缓存达到最大容量时，优先移除最长时间未被访问的数据条目，为新的数据条目腾出空间。这种策略基于“局部性原理”，即最近被访问过的数据项未来被再次访问的概率较高。

LRU 缓存的工作原理

LRU 缓存使用一种数据结构来同时维护数据条目的插入顺序和访问顺序。这通常通过结合使用哈希表和双向链表来实现：

哈希表用于快速查找和访问缓存中的数据条目，达到近乎 O(1) 的访问时间复杂度。
双向链表用于维护所有数据条目的访问顺序。链表的头部代表了最近被访问的数据，而链表的尾部代表了最久未被访问的数据。

核心操作

访问数据（get）:
当访问一个数据项时，如果该项在缓存中，则需要将其移动到双向链表的头部，表示该数据项是最近被访问过的。
如果数据项不在缓存中，则返回null或者相应的指示。
添加/更新数据（put）:
当插入一个新的数据项时，该数据项被放置在双向链表的头部，表示最近被访问过。同时，该数据项的键和寻址信息被存储在哈希表中。
如果缓存达到最大容量，则需要从双向链表的尾部移除一个数据项，并且在哈希表中删除相应的项。
如果插入的是一个现存的数据项（更新操作），则将该数据项移动到双向链表的头部，并更新哈希表中的值。

为何选择 LRU

LRU 缓存策略的优势在于其简洁而有效的机制，能够在保持缓存空间高效使用的同时，确保了频繁访问的数据可以快速被检索。这对于提高应用性能、降低数据访问延迟具有显著效果。

使用场景

LRU 缓存在各种场景中都有应用，特别是在需要快速访问数据的场合，如：

数据库查询缓存
Web 页面缓存
文件系统的缓存
内容分发网络（CDN）

总之，LRU 缓存是一种广泛使用的缓存淘汰策略，通过优先移除最长时间未被访问的数据项，它能有效管理有限的缓存空间，并提高数据访问效率。

一个简单的LRU缓存实现


import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

/**
 * A simple LRU cache implementation based on LinkedHashMap.
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> {
    private final LinkedHashMap<K, CacheEntry<V>> cache;
    private final int maxSize;
    private final long maxLifetimeMillis;

    /**
     * 构造器 LRUCache(final int maxSize, final long maxLifetime, final TimeUnit maxLifetimeUnit)：
     *
     * 创建一个 LRUCache 实例，并设置缓存的最大容量 maxSize 和元素的最大生存时间（maxLifetimeMillis，由 maxLifetime 和 maxLifetimeUnit 转换而来）。
     * 如果 maxSize 或 maxLifetime 是非正数，则会抛出 IllegalArgumentException 异常。
     * 缓存中元素的添加是基于 LinkedHashMap 的 access-order（访问顺序），即最近访问的元素会被放到队尾。
     * @param maxSize
     * @param maxLifetime
     * @param maxLifetimeUnit
     */
    public LRUCache(final int maxSize, final long maxLifetime, final TimeUnit maxLifetimeUnit) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize must be positive");
        }
        if (maxLifetime <= 0) {
            throw new IllegalArgumentException("maxLifetime must be positive");
        }
        this.maxSize = maxSize;
        this.maxLifetimeMillis = maxLifetimeUnit.toMillis(maxLifetime);
        this.cache = new LinkedHashMap<K, CacheEntry<V>>(maxSize, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<K, CacheEntry<V>> eldest) {
                long now = System.currentTimeMillis();
                V value = eldest.getValue().value;
                long creationTime = eldest.getValue().creationTime;
                // Remove the oldest item if either the cache size is exceeded
                // or if the oldest item's lifetime is expired
                return (size() > LRUCache.this.maxSize)
                        || ((now - creationTime) > LRUCache.this.maxLifetimeMillis);
            }
        };
    }

    /**
     * 将键值对存入缓存中，如果键或值为空则抛出 NullPointerException。
     * 如果缓存已满或某个元素过期，这个方法还会触发缓存中最旧的元素被清除（通过 LinkedHashMap 内部的 removeEldestEntry 方法定义）。
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        long now = System.currentTimeMillis();
        if (key == null || value == null) {
            throw new NullPointerException("key and value must not be null");
        }
        synchronized (cache) {
            cache.put(key, new CacheEntry<>(value, now));
        }
    }

    /**
     * 从缓存中获取键对应的值，如果不存在则存入默认值 defaultValue 并返回。
     * @param key
     * @param defaultValue
     * @return
     */
    public V get(K key, V defaultValue) {
        synchronized (cache) {
            V value = get(key);
            if (value == null) {
                put(key, defaultValue);
                return defaultValue;
            }
            return value;
        }
    }

    /**
     * 从缓存中移除指定键及其对应的值。
     * @param key
     */
    public void invalidate(K key) {
        synchronized (cache) {
            cache.remove(key);
        }
    }

    /**
     * 移除并返回缓存中指定键对应的值。
     * @param key
     * @return
     */
    public V remove(K key) {
        synchronized (cache) {
            CacheEntry<V> entry = cache.remove(key);
            return entry == null ? null : entry.value;
        }
    }

    /**
     * 根据给定的键获取对应的值，并根据元素的生存时间判断是否过期；如果没有过期，则返回值并更新元素在缓存中的位置（访问顺序），否则从缓存中删除该元素并返回 null。
     * @param key
     * @return
     */
    public V get(K key) {
        synchronized (cache) {
            long now = System.currentTimeMillis();
            CacheEntry<V> entry = cache.get(key);
            if (entry != null && (now - entry.creationTime) <= maxLifetimeMillis) {
                // LinkedHashMap access-order policy will move the entry to the end
                return entry.value;
            } else {
                cache.remove(key);
                return null;
            }
        }
    }

    /**
     * 分别返回缓存中所有值的集合。
     * @return
     */
    public Set<V> values() {
        synchronized (cache) {
            return cache.values().stream().map(e -> e.value).collect(Collectors.toSet());
        }
    }

    /**
     * 分别返回缓存中所有键的集合。
     * @return
     */
    public Set<K> keys() {
        synchronized (cache) {
            return cache.keySet();
        }
    }

    /**
     * 判断缓存中是否包含指定键的元素，同时检查该元素是否过期。
     * @param key
     * @return
     */
    public boolean containsKey(K key) {
        synchronized (cache) {
            return cache.containsKey(key) && (System.currentTimeMillis() - cache.get(key).creationTime) <= maxLifetimeMillis;
        }
    }

    /**
     * 清空缓存中的所有元素。
     */
    public void clear() {
        synchronized (cache) {
            cache.clear();
        }
    }

    /**
     * 获取缓存当前的大小。
     * @return
     */
    public int size() {
        synchronized (cache) {
            return cache.size();
        }
    }

    /**
     * 获取缓存当前的最大容量。
     * @return
     */
    public int getMaxSize() {
        return maxSize;
    }

    private static class CacheEntry<V> {
        final V value;
        final long creationTime;

        CacheEntry(V value, long creationTime) {
            this.value = value;
            this.creationTime = creationTime;
        }
    }
}