- 1Git 忽略文件的四种方式_git的exclude文件忽略文件夹
- 2【入门篇】本章包括创建云项目、数据库的使用、云存储管理、云函数的基本使用、实战举例（小程序之云函数开发入门到使用发布上线实操）_微信开发者工具云函数怎么用
- 3autojs- 联众识别_联众图像识别平台
- 4C#调用python脚本的方法步骤
- 5ubuntu18.04安装mysql8.0_ubuntu18安装mysql8
- 6【开发随记】国密SM2的简单运用和踩坑_sm2.js概率解密失败
- 7〔002〕虚幻 UE5 发送 get、post 请求、读取 json 文件_ue5 json
- 8【C语言篇】函数递归详解+汉诺塔问题、小青蛙跳台阶实例详解+浅谈递归优缺点_函数递归调用详解
- 9APOLLO配置中心_apollo 获取配置时指定集群
- 10C#使用数据存储方式访问数据库_c#数据库储存代码
你了解Redis 内存淘汰机制吗？你能讲一下LRU算法和LFU算法吗，如果让你分别实现你会怎么实现？_你了解redis 内存淘汰机制吗?你能讲一下lru算法和lfu算法吗,如果让你分别实现你会
赞
踩
最近面试的时候被问到Redis的内存淘汰机制、LRU算法、LFU算法实现，以及Redis 中如何实现LRU算法、LFU算法，现在进行简单的总结
一：Redis 内存淘汰策略
当 Redis 的运行内存已经超过 Redis 设置的最大内存之后，则会使用内存淘汰策略删除符合条件的 key，以此来保障 Redis 高效的运行。
1.Redis 内存淘汰策略有哪些？
1)noeviction：（Redis3.0之后，默认的内存淘汰策略） ：它表示当运行内存超过最大设置内存时，不淘汰任何数据，这时如果有新的数据写入，会报错通知禁止写入。
2）volatile-random：随机淘汰设置了过期时间的任意键值；
3）volatile-ttl：优先淘汰更早过期的键值；
4）volatile-lru（Redis3.0 之前，默认的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最久未使用的键值；
5）volatile-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最少使用的键值；
6）allkeys-random：随机淘汰任意键值;
7）allkeys-lru：淘汰整个键值中最久未使用的键值；
8）allkeys-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰整个键值中最少使用的键值；
2.如何查看Redis 使用的内存淘汰策略？
使用 config get maxmemory-policy 命令，如下图
3.如何修改Redis 内存淘汰策略
方式一：使用config set maxmemory-policy命令
127.0.0.1:6379> config set maxmemory-policy volatile-random
OK
127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "volatile-random"
127.0.0.1:6379>
- 1
- 2
- 3
- 4
- 5
- 6
方式二：修改Redis 配置文件，设置maxmemory-policy 的内容，后面跟着具体的策略。
二：LRU实现原理
1.什么是LRU算法？
LRU是一种基于时间的内存淘汰策略(最近最少使用，会淘汰掉长时间不使用的数据)。它假设最近被访问的数据在未来也更有可能被访问，而较长时间未被访问的数据更可能不再被使用。根据这个策略，LRU算法会淘汰最久未被访问的数据，以腾出内存空间。
以下是一个LRU算法示意图：
- 向一个缓存空间依次插入三个数据A/B/C，填满了缓存空间；
- 读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
- 插入数据D的时候，由于缓存空间已满，触发了LRU的淘汰策略，数据B被移出，缓存空间只保留了D/A/C。
2.如何实现LRU算法？
LRU算法比较核心的思想是要记录最近被访问的、最早被访问的数据，在访问数据和修改数据(编辑、新增、删除)数据时，该部分数据就会变成最新的数据，内存不够时会把最早被访问的数据删除掉。
很快我们锁定了List，最近被访问的数据(最新的数据) 可以存在在List的第一个位置，最早被访问的(最老的数据)可以存放在List的最后一个位置。但是由于数据的访问、数据的修改都会导致数据位置的变动，所以使用List会存在一定的性能问题，因此我们可以采用一个双向链表来暂时解决该问题。
因此我们可以采用一个双向链表维护缓存的上一次使用时间，并且可以使数据插入/删除等操作的时间复杂度是O(1)。此外当链表越来越长时，我们访问某个元素时需要遍历访问，性能较差，因此新增一个哈希表，记录链表节点的映射关系，解决如果只使用双向链表每次判断key是否存在时都需要遍历整个链表的问题。
3.手写一个LRU算法
3.1 LRU算法核心逻辑
因为访问数据、修改数据都会使元素的位置发生改变，因此可以分开讨论。
1）读场景：根据key读取数据，首先会判断哈希表中是否存在该key
- key不存在，返回-1；
- key存在，在原链表中删除该节点，并把该重新插入链表的头部；
2）写场景：根据key读取数据，首先会判断哈希表中是否存在该key
- key不存在，判断容量是否达上限，如果没达上限则根据入参构造新节点，把该节点插入到链表头部，之后在哈希表中新增该映射，value是该节点；
- key不存在，判断容量是否达上限，如果已达上限，把该链表的最后一个节点删除，并删除最后一个节点在哈希表的映射关系，然后根据入参构造新节点，把该节点插入到链表头部，之后在哈希表中新增该映射，value是该节点；
- key存在，更新哈希表中的value值，并在原链表中删除该节点，并把该节点重新插入链表的头部；
3.2 编码实现
关键属性：
private Map<Integer, Node> cache; // 哈希表用于快速查找节点
private int capacity; // LRU缓存的容量
private Node head; // 双向链表的头节点
private Node tail; // 双向链表的尾节点
- 1
- 2
- 3
- 4
读缓存，先判断是否存在该key，不存在则返回-1，存在则把该元素从原链表删除并添加到链表头部
public int get(int key) {
if (!cache.containsKey(key)) {
return -1; // 如果缓存中不存在该键，则返回 -1
}
Node node = cache.get(key); // 获取节点
moveToHead(node); // 将节点移到链表头部，表示最近访问过
return node.value; // 返回节点的值
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
写缓存，key如果存在则更新value，则把该元素从原链表删除并添加到链表头部。如果不存在，并且缓存没满则构建新节点并添加到链表头部、维护哈希表映射，否则先会进行数据淘汰(原链表删除、哈希表映射删除)，再把数据添加到链表头部、新增哈希表映射关系等
public void put(int key, int value) {
if (cache.containsKey(key)) { // 如果缓存中已经存在该键
Node node = cache.get(key); // 获取节点
node.value = value; // 更新节点的值
moveToHead(node); // 将节点移到链表头部，表示最近访问过
} else { // 如果缓存中不存在该键
if (cache.size() == capacity) { // 如果缓存已满
Node lastNode = tail.prev; // 获取尾部节点，即最久未使用的节点
removeNode(lastNode); // 移除尾部节点
cache.remove(lastNode.key); // 从缓存中移除该节点的键
}
Node newNode = new Node(key, value); // 创建新节点
cache.put(key, newNode); // 将节点加入缓存
addNode(newNode); // 将节点添加到链表头部
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
public class LRUCacheTest {
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
System.out.println(cache.get(1)); // 输出 1
cache.put(4, 4); // 缓存已满，最近最少使用的节点（2）将被删除
System.out.println(cache.get(2)); // 输出 -1，因为2已被删除
cache.put(5, 5); // 缓存已满，最近最少使用的节点（3）将被删除
System.out.println(cache.get(3));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
验证：
1）构建三个节点的缓存，分别为：节点1(key是1，value是1)、节点2(key是2，value是2)、节点3(key是3，value是3)；
2）输出第一个节点，查询结果；
3）新增一个节点4(key是4，value是4)，查询节点2；
4)新增一个节点5(key是5，value是5)，查询节点3；
2）执行的结果是1，此时容量刚好为3个节点，不触发淘汰机制；
3）执行的结果是-1，因为经过步骤2)后 链表中的排序是 1、3、2，因此会把节点2给删除，并新增节点4，所以访问节点2的数据时返回-1；
4）执行的结果是-1，因为经过步骤3)后 链表中的排序是 4、1、3，因此会把节点3给删除，并新增节点5，所以访问节点3的数据时返回-1；
4.Redis 是如何实现LRU算法？
由官方文档介绍，Redis所实现的是一种近似的LRU算法，每次随机选取一批数据进行LRU淘汰，而不是针对所有的数据，通过牺牲部分准确率来提高LRU算法的执行效率。
Redis 内部只使用了Hash表缓存数据，但是没有创建一个专门针对LRU算法的双向链表。这样做有几个好处：
- Redis是随机抽取一批数据去按照淘汰策略排序，不再需要对所有数据排序、也不需要对数据所有都进行移位，带来性能的提升；
- 淘汰策略改变时，不至于会影响到所有数据的改变；
Redis 中的LRU算法实现基于redisObject底层数据结构，成员变量lru字段用于记录了此key最近一次被访问的LRU时钟(server.lruclock)，每次Key被访问或修改都会引起lru字段的更新。
默认的LRU时钟单位是秒，可以修改LRU_CLOCK_RESOLUTION宏来改变单位，LRU时钟更新的频率也和server.hz参数有关。
LRU算法在淘汰数据过程中可能会淘汰掉热点数据，因此LFU算法应运而生。
三：LFU实现原理
1.什么是LFU算法？
LFU是一种基于访问频率的内存淘汰策略（最不经常使用，会淘汰掉使用次数最少的数据）。它假设经常被访问的数据在未来仍然频繁被访问，而较少被访问的数据更可能不再被使用。根据这个策略，LFU算法会淘汰访问频率最低的数据，以释放内存空间。
2.如何实现LFU算法？
实现LFU算法的一种常见方法是使用三个数据结构：
- 哈希表（keyToValue）：用于存储键值对，提供快速的键值查找功能。
- 哈希表（keyToFreq）：用于存储键的访问频率，记录每个键被访问的次数。
- 哈希表（freqToKeys）：用于存储相同访问频率的键的集合，以便快速获取具有相同访问频率的键。
LFU算法的实现步骤如下：
- 初始化缓存容量、最小访问频率为0以及上述三个哈希表。
- 当需要获取缓存中的数据项时，首先检查键是否存在于keyToValue哈希表中。如果不存在，则返回-1表示未找到；如果存在，则获取对应的值，并更新该键的访问频率。
- 当需要插入新的数据项时，首先检查缓存是否已满。如果已满，则根据LFU原则淘汰一个访问频率最低的数据项。然后将新的键值对添加到keyToValue哈希表中，并将访问频率设置为1，并将键添加到对应访问频率的键集合中。如果缓存未满，则直接将新的键值对添加到keyToValue哈希表中，并将访问频率设置为1，并将键添加到对应访问频率的键集合中。
- 当更新键的访问频率时，首先从原访问频率的键集合中移除该键。如果原访问频率的键集合为空且等于最小访问频率，则更新最小访问频率。然后将键添加到新访问频率的键集合中，并更新键的访问频率。
- 当需要淘汰数据项时，从最小访问频率的键集合中选择一个键进行淘汰，并从keyToValue、keyToFreq和freqToKeys哈希表中移除该键。
3.手写一个LFU算法
关键属性，keyToValue用来存储数据、keyToFreq用来存储key的频率、freqToKeys用来存储相同访问频率的键的集合
private Map<Integer, Integer> keyToValue; // 存储键值对的哈希表
private Map<Integer, Integer> keyToFreq; // 存储键的访问频率的哈希表
private Map<Integer, LinkedHashSet<Integer>> freqToKeys; // 存储相同访问频率的键的集合的哈希表
private int capacity; // 缓存容量
private int minFreq; // 最小访问频率
- 1
- 2
- 3
- 4
- 5
当我们再访问元素时，先判断数据是否存在(即keyToValue 是否存在)，如不存在返回-1，存在则获取数据并更新对应的频率
public int get(int key) {
if (!keyToValue.containsKey(key)) {
return -1; // 如果键不存在，则返回 -1
}
int value = keyToValue.get(key);
int freq = keyToFreq.get(key);
updateFreq(key, freq); // 更新键的访问频率
return value;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
更新数据时，也区分key是否存在的情况，具体如下
public void put(int key, int value) {
if (capacity <= 0) {
return; // 如果缓存容量为 0，则直接返回
}
if (keyToValue.containsKey(key)) {
keyToValue.put(key, value); // 如果键已存在，则更新值
int freq = keyToFreq.get(key);
updateFreq(key, freq); // 更新键的访问频率
} else {
if (keyToValue.size() >= capacity) {
evict(); // 如果缓存已满，则淘汰一个键
}
keyToValue.put(key, value); // 添加新的键值对
keyToFreq.put(key, 1); // 设置键的初始访问频率为 1
freqToKeys.putIfAbsent(1, new LinkedHashSet<>()); // 初始化访问频率为 1 的键集合
freqToKeys.get(1).add(key); // 将键添加到访问频率为 1 的键集合中
minFreq = 1; // 更新最小访问频率为 1
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
访问数据、修改数据都会进行数据的淘汰，可在freqToKeys数据淘汰，因为LinkedHashSet保证有序，因此每次淘汰时只需要把第一个元素淘汰即可
private void evict() {
LinkedHashSet<Integer> keys = freqToKeys.get(minFreq); // 获取最小访问频率的键集合
int evictKey = keys.iterator().next(); // 获取集合中的第一个键进行淘汰
keys.remove(evictKey); // 从键集合中移除被淘汰的键
keyToValue.remove(evictKey); // 从键值对哈希表中移除被淘汰的键值对
keyToFreq.remove(evictKey); // 从访问频率哈希表中移除被淘汰的键
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
验证：
public class LFUCacheTest {
public static void main(String[] args) {
// 创建一个容量为2的LFU缓存
LFUCache cache = new LFUCache(2);
// 添加键值对
cache.put(1, 1);
cache.put(2, 2);
// 获取键1的值，期望输出1
System.out.println(cache.get(1));
// 添加键3，此时缓存已满，将淘汰键2
cache.put(3, 3);
// 获取键2的值，期望输出-1（已被淘汰）
System.out.println(cache.get(2));
// 获取键3的值，期望输出3
System.out.println(cache.get(3));
// 添加键4，此时缓存已满，将淘汰键1
cache.put(4, 4);
// 获取键1的值，期望输出-1（已被淘汰）
System.out.println(cache.get(1));
// 获取键3的值，期望输出3
System.out.println(cache.get(3));
// 获取键4的值，期望输出4
System.out.println(cache.get(4));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
运行结果和预期一致，LFU算法淘汰的是访问频率最小的数据，那如果访问频率相同时淘汰哪部分的数据呢？
具体淘汰的策略由我们自己控制，这里频率相同时淘汰的是最早访问的那部分数据。
4.Redis 是如何实现LFU算法？
Redis使用一种近似的LFU算法，称为近似LFU（Approximate LFU）。这是为了减少内存消耗，因为精确实现LFU算法需要维护每个键的访问频率计数器，会占用大量内存。
在Redis中，近似LFU算法的实现主要依赖于两个关键的数据结构：LFU近似计数器和LFU时钟。
- LFU近似计数器：Redis使用一个固定大小的数组来存储LFU近似计数器。数组的每个索引对应一个桶，每个桶中存储了一组键。每当一个键被访问时，对应桶的计数器会增加。当需要淘汰键时，Redis会选择计数器最小的桶，并从该桶中淘汰一个键。
- LFU时钟：Redis使用一个全局的时钟来跟踪键的访问频率。时钟以固定的时间间隔进行递增。当时钟递增时，Redis会将当前桶的计数器值除以2，并将结果存储在下一个桶中。这样，访问频率较低的键会逐渐被淘汰。
需要注意的是，Redis的近似LFU算法是在内存中进行的，而不是在持久化存储中。当Redis重启时，近似LFU计数器会被重置，因此在重启后可能会出现一些冷启动的情况。
四：案例完整源码
1.LRU算法代码实现
public class LRUCache {
private Map<Integer, Node> cache; // 哈希表用于快速查找节点
private int capacity; // LRU缓存的容量
private Node head; // 双向链表的头节点
private Node tail; // 双向链表的尾节点
public LRUCache(int capacity) {
this.cache = new HashMap<>(capacity); // 初始化哈希表
this.capacity = capacity; // 初始化容量
this.head = new Node(-1, -1); // 初始化头节点
this.tail = new Node(-1, -1); // 初始化尾节点
head.next = tail; // 头节点的下一个节点是尾节点
tail.prev = head; // 尾节点的上一个节点是头节点
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1; // 如果缓存中不存在该键，则返回 -1
}
Node node = cache.get(key); // 获取节点
moveToHead(node); // 将节点移到链表头部，表示最近访问过
return node.value; // 返回节点的值
}
public void put(int key, int value) {
if (cache.containsKey(key)) { // 如果缓存中已经存在该键
Node node = cache.get(key); // 获取节点
node.value = value; // 更新节点的值
moveToHead(node); // 将节点移到链表头部，表示最近访问过
} else { // 如果缓存中不存在该键
if (cache.size() == capacity) { // 如果缓存已满
Node lastNode = tail.prev; // 获取尾部节点，即最久未使用的节点
removeNode(lastNode); // 移除尾部节点
cache.remove(lastNode.key); // 从缓存中移除该节点的键
}
Node newNode = new Node(key, value); // 创建新节点
cache.put(key, newNode); // 将节点加入缓存
addNode(newNode); // 将节点添加到链表头部
}
}
private void moveToHead(Node node) {
removeNode(node); // 先将节点从链表中移除
addNode(node); // 再将节点添加到链表头部
}
private void addNode(Node node) {
node.next = head.next; // 新节点的下一个节点是头节点的下一个节点
head.next.prev = node; // 头节点的下一个节点的上一个节点是新节点
head.next = node; // 头节点的下一个节点是新节点
node.prev = head; // 新节点的上一个节点是头节点
}
private void removeNode(Node node) {
node.prev.next = node.next; // 被移除节点的上一个节点的下一个节点是被移除节点的下一个节点
node.next.prev = node.prev; // 被移除节点的下一个节点的上一个节点是被移除节点的上一个节点
}
private class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
测试方法如下
public class LRUCacheTest {
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
System.out.println(cache.get(1)); // 输出 1
cache.put(4, 4); // 缓存已满，最近最少使用的节点（2）将被删除
System.out.println(cache.get(2)); // 输出 -1，因为2已被删除
cache.put(5, 5); // 缓存已满，最近最少使用的节点（3）将被删除
System.out.println(cache.get(3));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.LFU算法代码实现
public class LFUCache {
private Map<Integer, Integer> keyToValue; // 存储键值对的哈希表
private Map<Integer, Integer> keyToFreq; // 存储键的访问频率的哈希表
private Map<Integer, LinkedHashSet<Integer>> freqToKeys; // 存储相同访问频率的键的集合的哈希表
private int capacity; // 缓存容量
private int minFreq; // 最小访问频率
public LFUCache(int capacity) {
this.keyToValue = new HashMap<>();
this.keyToFreq = new HashMap<>();
this.freqToKeys = new HashMap<>();
this.capacity = capacity;
this.minFreq = 0;
}
public int get(int key) {
if (!keyToValue.containsKey(key)) {
return -1; // 如果键不存在，则返回 -1
}
int value = keyToValue.get(key);
int freq = keyToFreq.get(key);
updateFreq(key, freq); // 更新键的访问频率
return value;
}
public void put(int key, int value) {
if (capacity <= 0) {
return; // 如果缓存容量为 0，则直接返回
}
if (keyToValue.containsKey(key)) {
keyToValue.put(key, value); // 如果键已存在，则更新值
int freq = keyToFreq.get(key);
updateFreq(key, freq); // 更新键的访问频率
} else {
if (keyToValue.size() >= capacity) {
evict(); // 如果缓存已满，则淘汰一个键
}
keyToValue.put(key, value); // 添加新的键值对
keyToFreq.put(key, 1); // 设置键的初始访问频率为 1
freqToKeys.putIfAbsent(1, new LinkedHashSet<>()); // 初始化访问频率为 1 的键集合
freqToKeys.get(1).add(key); // 将键添加到访问频率为 1 的键集合中
minFreq = 1; // 更新最小访问频率为 1
}
}
private void updateFreq(int key, int freq) {
freqToKeys.get(freq).remove(key); // 从原访问频率的键集合中移除键
if (freqToKeys.get(freq).isEmpty() && freq == minFreq) {
minFreq++; // 如果原访问频率的键集合为空且等于最小访问频率，则更新最小访问频率
}
freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>()); // 初始化新访问频率的键集合
freqToKeys.get(freq + 1).add(key); // 将键添加到新访问频率的键集合中
keyToFreq.put(key, freq + 1); // 更新键的访问频率
}
private void evict() {
LinkedHashSet<Integer> keys = freqToKeys.get(minFreq); // 获取最小访问频率的键集合
int evictKey = keys.iterator().next(); // 获取集合中的第一个键进行淘汰
keys.remove(evictKey); // 从键集合中移除被淘汰的键
keyToValue.remove(evictKey); // 从键值对哈希表中移除被淘汰的键值对
keyToFreq.remove(evictKey); // 从访问频率哈希表中移除被淘汰的键
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
测试方法如下
public class LFUCacheTest {
public static void main(String[] args) {
// 创建一个容量为2的LFU缓存
LFUCache cache = new LFUCache(2);
// 添加键值对
cache.put(1, 1);
cache.put(2, 2);
// 获取键1的值，期望输出1
System.out.println(cache.get(1));
// 添加键3，此时缓存已满，将淘汰键2
cache.put(3, 3);
// 获取键2的值，期望输出-1（已被淘汰）
System.out.println(cache.get(2));
// 获取键3的值，期望输出3
System.out.println(cache.get(3));
// 添加键4，此时缓存已满，将淘汰键1
cache.put(4, 4);
// 获取键1的值，期望输出-1（已被淘汰）
System.out.println(cache.get(1));
// 获取键3的值，期望输出3
System.out.println(cache.get(3));
// 获取键4的值，期望输出4
System.out.println(cache.get(4));
cache.put(3, 3);
cache.put(4, 4);
cache.put(4, 4);
cache.put(4, 4);
cache.put(4, 4);
cache.put(3, 3);
cache.put(3, 3);
cache.put(5, 5);
System.out.println(cache.get(4));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
