正文 

当前位置： 首页 > 开发 > java教程

redis前传自己手写一个lru策略|redis淘汰策略(代码片段)

烟花散尽13141 烟花散尽13141     2022-12-08     694

关键词：

一、题目描述

146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化LRU缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

二、思路分析

第一想法

  • 刚看到本题时没有多想就觉得会用到队列，因为队列FIFO可以做到淘汰末尾数据，但是仔细一想本题是需要淘汰最近最少使用数据，如果仅仅是最近的数据那么队列很容易实现。加上使用频率就涉及到数据的频繁挪动。很明显队列是无法完成的。
  • 那么有没有一种顺序添加的数据，每次在获取之后就会将数据前移至一端呢？答案是有的！LinkedHashMap
  • LinkedHashMap 不熟悉的朋友们可以简单的将它理解成HashMap 。 下图展示了HashMap的存储结构

  • 上述的元素我这里做了个动画演示全过程！！！

  • 而LinkedHashMap只是多了一条链表串起里面的元素

  • 这也是为什么LinkedHashMap是按照顺序存储的。但是LinkedHahsMap也无法做到按照使用频率进行排序啊？大家都知道他是按照添加顺序排序的！！！

*LinkedHashMap*改造

  • 原生的LinkedHashMap的确无法满足情况，但是我们稍微看下源码能够发现在put之后都会执行下afterNodeInsertion 这个方法。这也是HashMap留给LinkedHashMap做的扩展！

  • removeNode 就是将最前面的数据。想要进入这个方法就需要removeEldestEntry判断。LinkedHashMap默认是false . 所以我们只需要重写他就行了。但是还是在get值的时候如何保值在最后面呢？我们仔细看下源码就能够发现在get中有这个一个方法afterNodeAccess 。他的作用就是将get的元素移位值后面。正好符合我们LRU的策略特征

  • 综上！我们借助LinkedHashMap就非常容易的实现了LRU策略！

自己实现

  • 但是本题的意思是想考察我们自己是如何实现的，而不是巧妙对现有的工具改造的！不过上面对LinkedHashMap的确改造的很巧这是不可否认的！下面我们就尝试自己来实现下这种方式！

  • 首先我们需要确定需要用到Hash结合链表来实现。Hash我们自然使用HashMap来存储数据为的就是方便定位数据。定位到数据就需要操作链表将数据实时移位值链表尾部，每次淘汰是将链表首位移除既可。为了方便我们操作链表这里的链表肯定是双链表的！

链表单元

  • 首先我们定义一个内部类！用于链表的基本单元。里面存储了key,value方便根据Hash中存储的内容找到节点！preNode，nextNode分别指向前后节点

  • 在构建器中初始化容量和链表大小，并初始化边界节点方便我们操作节点中移位和删除。

  • 在获取数据时没有添加就返回-1 ， 已经添加的数据则将该数据对应的node节点移动到链表的尾部。

  • 在put中当第一次添加我们需要维护链表大小并进行检测是否需要进行淘汰数据，如果不是第一次添加我们只需奥更新值和对应node在链表中的位置即可

方法名作用
addToTail将节点添加值链表尾部
moveToTail将已经存在于链表中的节点移动到链表的尾部
removeHeadNode删除链表中第一个节点，注意是边界节点后第一个节点

四、总结

  • 虽然执行时间和内存消耗有点高！但是我就是不优化。
  • 本题主要就是在链表的移动上面会复杂点。我们需要按照添加顺序和使用频率两个维度进行维护他们之间的顺序。只要这个顺序维护好，就没啥问题了！

手写redis淘汰策略中lru算法（删除最近未使用的值）java版(代码片段)

1.题目描述：请见leetcode（LRU缓存机制）2.实现思路：通过HashMap+双向链表实现HashMap：保证查询的时间复杂度是O（1）双向链表：链表特性，增删元素速度快，链表由头节点+中间节点+... 查看详情

redis的lru算法(代码片段)

...虽然有Redis内存使用告警，但是了解一下Redis的缓存使用策略还是很有好处的。下面是生产环境下Redis使用策略：最大可用内存限制为4GB，采用allkeys-lru删除策略。所谓删除策略：当redis使用已经达到了最大内存，比如4GB时，如果... 查看详情

redis中的lru淘汰策略分析(代码片段)

...消耗问题。Redis会删除过期键以释放空间，过期键的删除策略有两种：惰性删除：每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。定期删除：每隔一段时间，程序... 查看详情

面试官说，听说你了解redis，手写一个lru算法吧

LRU是什么缓存命中率是缓存系统的非常重要指标，如果缓存系统的缓存命中率过低，将会导致查询回流到数据库，导致数据库的压力升高。LRU(LeastRecentlyUsed)即最近最少使用的数据需要被淘汰，属于典型的内存淘汰... 查看详情

redis内存淘汰策略

...到的就会放入表头，表尾就是最少被访问的。LRU算法需要一个双向链表来记录数据的最近被访问顺序，但是出于节省内存的考虑，Redis的LRU算法并非完整的实现。Redis的LRU并不维护队列，它会提供一个待淘汰候选key的pool，里面默... 查看详情

redis内存

...少使用的key。Redis为了实现近似LRU算法，给每个key增加了一个额外增加了一个24bit的字段，用来存储该key最后一次被访问的时间。Redis3.0对近似LRU的优化Redis3.0对近似LRU算法进行了一些优化。新算法会维护一个候选池（大小为16）... 查看详情

redis的缓存淘汰策略lru与lfu

参考技术ARedis缓存淘汰策略与Redis键的过期删除策略并不完全相同，前者是在Redis内存使用超过一定值的时候（一般这个值可以配置）使用的淘汰策略；而后者是通过定期删除+惰性删除两者结合的方式淘汰内存过期键的。这里参... 查看详情

java从零开始手写redislru缓存淘汰策略详解(代码片段)

前言java从零手写实现redis（一）如何实现固定大小的缓存？java从零手写实现redis（三）redisexpire过期原理java从零手写实现redis（三）内存数据如何重启不丢失？java从零手写实现redis（四）添加监听器java从零手写实现redis（五）过... 查看详情

redis内存满了怎么办？

...记录来进行淘汰数据。​它的核心的思想就是：假如一个key值在最近很少被使用到，那么在将来也很少会被访问。​实际上Redis实现的LRU并不是真正的LRU算法，也就是名义上我们使用LRU算法淘汰键，但是实际上被淘汰的键... 查看详情

吃透redis：缓存淘汰篇-lru算法(代码片段)

...#xff0c;当内存使用达到了一定阈值，就会触发缓存淘汰策略，这和Redis配置文件redis.conf中的两个配置参数有关：maxmemory，该配置项设定了Redisserver可以使用的最大内存容量，一旦server使用的实际内存量超出该阈... 查看详情

吃透redis：缓存淘汰篇-lru算法(代码片段)

...#xff0c;当内存使用达到了一定阈值，就会触发缓存淘汰策略，这和Redis配置文件redis.conf中的两个配置 查看详情

吃透redis：缓存淘汰篇-lru算法(代码片段)

...#xff0c;当内存使用达到了一定阈值，就会触发缓存淘汰策略，这和Redis配置文件redis.conf中的两个配置 查看详情

redis内存满了怎么办，redis导致系统内存爆满(代码片段)

...大小。一般的项目maxmemory设置为3~5G即可，也可以根据自己服务器内存大小进行配置。maxmemory4G二、命令通过命令修改，链接redis服务通过命令动态修改内存大小。1//设置Redis最大占用内存大小为100M2127.0.0.1:6379>configsetmaxme... 查看详情

redis源码六-redis中的缓存淘汰策略处理分析(代码片段)

...整体处理流程和redis的定期清理。都没有说到redis的过期策略。这次我来探究一下。我们都知道redis的缓存淘汰策略有以下几种:noeviction无过期策略，内存满了就直接异常volatile-lru对有过期时间的key进行lru淘汰（越长时间没... 查看详情

redis淘汰策略

...淘汰机制进行淘汰。volatile-ttl，删除生存时间最近的一个键。noeviction(默认)，不删除键，值返回错误。主要是4种算法，针对不同的key,形成的策略。算法：lru最近很少的使用的key（根据时间，最不常用... 查看详情

redis提供6种数据淘汰策略(代码片段)

...有用的。譬如，在一台8G机子上部署了4个redis服务点，每一个服务点分配1.5G的内存大小，减少内存紧张的情况，由此获取更为稳健的服务。6中淘汰策略redis内存数据集大小上升到一定大小的时候，就会施行数据淘汰策略。redis提... 查看详情

缓存数据库redis之三：内存淘汰策略及优化(代码片段)

目录一、Redis的内存淘汰策略  1.1.概念  1.2.策略一：全局的键空间选择性移除  1.3.策略二：设置过期时间的键空间选择性移除  1.4.LRU、LFU和volatile-ttl都是近似随机算法 1.4.1.LRU算法 1.4.2.LFU算法1.5.过期删除策略1.6.AOF... 查看详情

缓存数据库redis之三：内存淘汰策略及优化(代码片段)

目录一、Redis的内存淘汰策略  1.1.概念  1.2.策略一：全局的键空间选择性移除  1.3.策略二：设置过期时间的键空间选择性移除  1.4.LRU、LFU和volatile-ttl都是近似随机算法 1.4.1.LRU算法 1.4.2.LFU算法1.5.过期删除策略1.6.AOF... 查看详情