厉害了,自己动手实现 LRU 缓存机制!
Java技术栈
共 7928字,需浏览 16分钟
· 2021-05-15
点击关注公众号,Java干货及时送达
前言
最近在逛博客的时候看到了有关Redis方面的面试题,其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制,然后找了这方面的一些资料与大家分享一下。
第一种实现(使用LinkedHashMap)
public class LRUCache {
int capacity;
Map<Integer,Integer> map;
public LRUCache(int capacity){
this.capacity = capacity;
map = new LinkedHashMap<>();
}
public int get(int key){
//如果没有找到
if (!map.containsKey(key)){
return -1;
}
//找到了就刷新数据
Integer value = map.remove(key);
map.put(key,value);
return value;
}
public void put(int key,int value){
if (map.containsKey(key)){
map.remove(key);
map.put(key,value);
return;
}
map.put(key,value);
//超出capacity,删除最久没用的即第一个,或者可以复写removeEldestEntry方法
if (map.size() > capacity){
map.remove(map.entrySet().iterator().next().getKey());
}
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(10);
for (int i = 0; i < 10; i++) {
lruCache.map.put(i,i);
System.out.println(lruCache.map.size());
}
System.out.println(lruCache.map);
lruCache.put(10,200);
System.out.println(lruCache.map);
}
第二种实现(双链表+hashmap)
public class LRUCache {
private int capacity;
private Map<Integer,ListNode>map;
private ListNode head;
private ListNode tail;
public LRUCache2(int capacity){
this.capacity = capacity;
map = new HashMap<>();
head = new ListNode(-1,-1);
tail = new ListNode(-1,-1);
head.next = tail;
tail.pre = head;
}
public int get(int key){
if (!map.containsKey(key)){
return -1;
}
ListNode node = map.get(key);
node.pre.next = node.next;
node.next.pre = node.pre;
return node.val;
}
public void put(int key,int value){
if (get(key)!=-1){
map.get(key).val = value;
return;
}
ListNode node = new ListNode(key,value);
map.put(key,node);
moveToTail(node);
if (map.size() > capacity){
map.remove(head.next.key);
head.next = head.next.next;
head.next.pre = head;
}
}
//把节点移动到尾巴
private void moveToTail(ListNode node) {
node.pre = tail.pre;
tail.pre = node;
node.pre.next = node;
node.next = tail;
}
//定义双向链表节点
private class ListNode{
int key;
int val;
ListNode pre;
ListNode next;
//初始化双向链表
public ListNode(int key,int val){
this.key = key;
this.val = val;
pre = null;
next = null;
}
}
}
像第一种方式,如果复写removeEldestEntry会更简单,这里简单的展示一下
public class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
另外,关注公众号Java技术栈,在后台回复:面试,可以获取我整理的 Redis 系列面试题和答案,非常齐全。
原文链接:https://blog.csdn.net/Grady00/article/details/115168822
版权声明:本文为CSDN博主「拉霍拉卡」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
关注Java技术栈看更多干货
评论
用 Shader 实现旗帜飘扬动画效果
我觉得对于刚入门 3D 编程的朋友来说,如果能够完成代码创建模型数据->创建材质->编写Shader动画这一系列,想必会有满满的成就感。今天就用 Cocos Creator 的 utils.MeshUtils.createMesh 接口,带大家感受一下这个流程。这个流程不仅可以用于新手学
COCOS
2
请问哪位大佬有空?我自己搞不定pycharm安装调试了?
点击上方“Python共享之家”,进行关注回复“资源”即可获赠Python学习资料今日鸡汤残云归太华,疏雨过中条。大家好,我是Python进阶者。一、前言前几天在Python最强王者交流群【斌】问了一个Python环境安装的问题,请问哪位大佬有空?我自己搞不定pycharm安装调试了。二、实现过程这
IT共享之家
0
PyPy为什么能让Python比C还快?一文了解内在机制
我的小册:(小白零基础用Python量化股票分析小册) ,原价299,限时特价2杯咖啡,满100人涨10元。来源:机器之心「如果想让代码运行得更快,您应该使用 PyPy。」—— Python 之父 Guido van Rossum对于研究人员来说,迅速把想法代码化并查看其是否行得通至关重要。Pyth
菜鸟学Python
0
如何动手做出一个 CPU,很简单
将Python客栈设为“星标⭐”第一时间收到最新资讯来源:无聊的闪客纯手工打造一个 CPU 这个事儿。在电子专业的同学眼里,很容易。在计算机专业的同学眼里,稍稍有点复杂,有的专业课的实验课可能会带着同学做一个,或者用 Logisim 这样的仿真软件去模拟实现一个。在非计算机专业的同学眼里,就有点不敢
Python客栈
0
图解 transformer 中的自注意力机制
↓推荐关注↓本文将将介绍注意力的概念从何而来,它是如何工作的以及它的简单的实现。注意力机制在整个注意力过程中,模型会学习了三个权重:查询、键和值。查询、键和值的思想来源于信息检索系统。所以我们先理解数据库查询的思想。假设有一个数据库,里面有所有一些作家和他们的书籍信息。现在我想读一些Rabindra
Python学习与数据挖掘
0
SpringBoot+Minio实现上传凭证、分片上传、秒传和断点续传
关注我们,设为星标,每天7:40不见不散,架构路上与您共享回复架构师获取资源大家好,我是你们的朋友架构君,一个会写代码吟诗的架构师。Spring Boot整合Minio后,前端的文件上传有两种方式:1、文件上传到后端,由后端保存到Minio这种方式好处是完全由后端集中管理,可以很好的做到、身份验证、
Java架构师社区
0
Redis 是怎么从单体架构发展到分布式缓存的?
图解学习网站:https://xiaolincoding.comRedis 架构是如何一步一步发展到今天的样子的?2010 年 - 单体 RedisRedis 1.0 于 2010 年发布,当时的架构非常简单。它通常用作业务应用程序的缓存。不过,Redis 将数据存储在内存中。当我们重启 Redis
小林coding
10
超越原生,散点图实现华夫饼图
之前我们介绍过了如何使用新卡片图实现华夫饼图。参考:超越原生,PowerBI 华夫饼图实现但是利用卡片图实现的华夫饼图有一些缺点,形状之间的大小跟间距不太好把握,而且有时形状大一点的话显示就会不正常,需要做出二次调整。今天给大家介绍一种原生视觉对象生成华夫饼图的更佳方案,既简单又美观。上图是利用散点
PowerBI战友联盟
2