缓存实现

相关源文件

• src/main/java/com/thealgorithms/datastructures/bloomfilter/BloomFilter.java
• src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java
• src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java
• src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java
• src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java
• src/test/java/com/thealgorithms/datastructures/bloomfilter/BloomFilterTest.java
• src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/caches/LRUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/caches/MRUCacheTest.java
• src/test/java/com/thealgorithms/datastructures/crdt/LWWElementSetTest.java

此页面记录了仓库中提供的各种缓存实现数据结构。缓存是通过将频繁或最近访问的数据随时可用，从而优化临时存储机制来提高性能。本文件涵盖了代码库中实现的各种缓存淘汰策略，并解释了它们的内部工作原理、使用模式和性能特征。

缓存机制概述

该仓库实现了三种主要的缓存策略，每种策略都有不同的淘汰策略：

1. LFU (Least Frequently Used，最少使用)：淘汰使用频率最低的项目。
2. LRU (Least Recently Used，最近最少使用)：淘汰最长时间未被访问的项目。
3. MRU (Most Recently Used，最近最常用)：优先淘汰最近最常使用的项目。

此外，还记录了与缓存相关的概率性数据结构：

• 布隆过滤器 (Bloom Filter)：一种空间效率高的概率性数据结构，用于成员资格测试。
• LWW Element Set：一种无冲突复制数据类型 (CRDT)，它使用时间戳来管理并发操作。

缓存架构图

来源：src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java src/main/java/com/thealgorithms/datastructures/bloomfilter/BloomFilter.java src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java

缓存淘汰策略

当缓存达到容量时，它必须删除（淘汰）现有条目以为新条目腾出空间。用于决定淘汰哪些条目的策略称为淘汰策略。

下表比较了仓库中实现的各种淘汰策略：

缓存类型	淘汰策略	最佳用例	实现
LFU 缓存	优先淘汰访问频率最低的项目。	当访问频率比最近访问更重要时。	使用频率计数器和双向链表。
LRU 缓存	优先淘汰最近未被访问的项目。	通用的缓存，具有时间局部性。	使用双向链表跟踪访问顺序。
MRU 缓存	优先淘汰最近最常使用的项目。	当旧项目更有可能再次被访问时。	类似于 LRU，但具有反向淘汰逻辑。

来源：src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java6-25 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java6-37 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java6-18

LFU 缓存 (Least Frequently Used，最少使用)

LFU 缓存将在达到容量时淘汰最不常用的项目。每个项目都有一个在被访问时增加的频率计数器。当缓存已满且需要添加新项目时，将淘汰频率计数器最低的项目。

内部结构

来源：src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java26-33 src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java54-58

实现细节

LFUCache 类使用：

• 一个 HashMap 来存储键到节点的映射，以实现 O(1) 的查找时间。
• 一个双向链表，用于按频率顺序维护节点。
• 一个 Node 内部类，用于存储键、值、频率计数和相邻节点的链接。

关键操作

• get(K key)：检索键的值，增加其频率，并重新定位节点。
• put(K key, V value)：添加或更新键值对，并在需要时淘汰最不常用的项目。

来源：src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java89-124 src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java132-184

LFU 使用示例

根据测试文件，以下是使用 LFU 缓存的方法：

来源：src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java40-64

LRU 缓存 (Least Recently Used，最近最少使用)

LRU 缓存将在达到容量时淘汰最近最少使用的项目。每次访问一个项目时，它都会被移动到“最近使用”的位置。当缓存已满时，将淘汰“最近最少使用”位置的项目。

内部结构

来源：src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java42-47 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java186-234

实现细节

LRUCache 使用：

• 一个 HashMap 实现 O(1) 查找。
• 一个双向链表来维护访问顺序。
• 链表的头部包含最近最少使用的项目。
• 链表的尾部包含最近最常用的项目。

每次缓存操作都会将访问的项目移至尾部（最近最常用的位置）。

来源：src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java107-140 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java148-184 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java77-86

LRU 使用示例

来源：src/test/java/com/thealgorithms/datastructures/caches/LRUCacheTest.java38-60

MRU 缓存 (Most Recently Used，最近最常用)

MRU 缓存实现了与 LRU 相反的策略——它首先淘汰最近最常用的项目。这在旧条目比最近访问的条目更有可能被再次访问的情况下很有用。

内部结构

MRUCache 的内部结构与 LRUCache 类似，使用 HashMap 进行查找，并使用双向链表来跟踪访问顺序。

来源：src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java19-25 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java182-229

MRU 与 LRU 淘汰策略比较

来源：src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java76-87 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java77-86

MRU 使用示例

来源： src/test/java/com/thealgorithms/datastructures/caches/MRUCacheTest.java70-90

相关数据结构

布隆过滤器

虽然布隆过滤器（Bloom Filter）不属于传统意义上的缓存，但它提供了一种空间效率高的方式来测试一个元素是否属于一个集合，因此具有与缓存相关的目的。它可以用于缓存的前端，以避免查找那些确定不存在的项。

布隆过滤器保证没有假阴性（如果它说一个项不在集合中，那它确实不在），但可能会产生假阳性。

来源： src/main/java/com/thealgorithms/datastructures/bloomfilter/BloomFilter.java5-14 src/main/java/com/thealgorithms/datastructures/bloomfilter/BloomFilter.java15-138

LWW 元素集（最后写入获胜）

LWW 元素集是一种无冲突的复制数据类型（CRDT），用于分布式环境中管理集合。它维护两个集合——一个添加集和一个删除集，并带有时间戳，以在发生并发操作时确定“获胜者”。

此数据结构特别适用于需要协调并发操作的分布式系统。

来源： src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java7-21 src/main/java/com/thealgorithms/datastructures/crdt/LWWElementSet.java23-127

性能特征

下表总结了缓存实现的性能特征

操作	LFU 缓存	LRU 缓存	MRU 缓存	布隆过滤器
get/查找	O(1)	O(1)	O(1)	O(k)*
put/插入	O(1)	O(1)	O(1)	O(k)*
Space键	O(n)	O(n)	O(n)	O(m)**

* k 是哈希函数的数量
** m 是位数组的大小（通常远小于 O(n)，n 为元素数量）

来源： src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java13-15 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java11-17 src/main/java/com/thealgorithms/datastructures/bloomfilter/BloomFilter.java14-71

使用指南

在选择缓存实现时，请考虑

1. 访问模式:

   • 当您希望保留经常访问的项而不管其最近性如何时，请使用 LFU
   • 对于通用缓存，请使用 LRU，因为最近的访问表明未来可能还会访问
   • 当旧项比最近访问过的项更可能被需要时，请使用 MRU

2. 空间约束:

   • 标准缓存（LRU、LFU、MRU）存储实际项
   • 布隆过滤器仅存储概率性的成员信息（不存储项本身）

3. 分布式系统:

   • LWW 元素集专为具有并发操作的分布式环境而设计

每个缓存实现都提供相同的核心接口，具有 get(key) 和 put(key, value) 方法，这使得它们在客户端代码中可以互换使用，但针对不同的访问模式具有不同的性能特征。

来源： src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java89-124 src/main/java/com/thealgorithms/datastructures/caches/LRUCache.java107-167 src/main/java/com/thealgorithms/datastructures/caches/MRUCache.java95-130