简单的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 expiredreturn (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 endreturn 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;}}
}