设计并实现一个并发安全的LRU(Least Recently Used,最近最少使用)缓存结构

本文主要是介绍设计并实现一个并发安全的LRU(Least Recently Used,最近最少使用)缓存结构,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 前言
    • 实战演示
    • 写在最后

前言

相信很多人都使用过LinkedHashMap,LinkedHashMap中的removeEldestEntry可以删除老旧的元素,我们可以以此来实现一个LRU缓存结构,并结合java中JUC包中的各种多线程锁机制来保证多线程安全。

以下是我遇见过的一个高级面试题:

【面试题】设计并实现一个并发安全的LRU(Least Recently Used,最近最少使用)缓存结构。要求支持以下操作:
get(key):如果键存在于缓存中,则获取其对应的值(总是返回最新添加的值),否则返回-1。
put(key, value):如果键已经存在,则更新其对应的值;如果键不存在,并且缓存未满,则添加该键值对到缓存中;如果缓存已满,则移除最近最少使用的键值对,然后再将新的键值对添加到缓存。

在这里插入图片描述

实战演示

可以采用LinkedHashMap的removeEldestEntry方法删除需要淘汰的元素,并直接使用map的get/put方法。

模拟代码

import java.util.LinkedHashMap;
import java.util.Map;/*** LRUCache* @author senfel* @date 2024/2/26 12:50*/
public class LRUCache<K, V> {private final int capacity;private LinkedHashMap<K, V> cache;public LRUCache(int capacity) {this.capacity = capacity;// 设置访问顺序和插入顺序一致,且当容量达到阈值时自动删除最近最少使用的项this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}};}/*** get* @author senfel* @date 2024/2/26 12:52* @return V */public V get(K key) {synchronized (cache) {return cache.getOrDefault(key, null);}}/*** put* @author senfel* @date 2024/2/26 12:52* @return void*/public void put(K key, V value) {synchronized (cache) {cache.put(key, value);}}
}

上述代码实现了一个基本的LRU缓存结构,但get方法在key不存在时返回null而不是-1,并且没有完全解决并发访问问题。而且我们在获取到已经存在的是数据后并没有刷新数据,也就是并没有实现醉经最少使用的淘汰策略。

下面是更完善的版本,包含正确的get方法逻辑以及线程安全的put和get操作,以及在获取到数据后将数据重新刷新了。

优化后的代码

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.LinkedHashMap;
import java.util.Map;
/*** LRUCache* @author senfel* @date 2024/2/26 12:55*/
public class LRUCache<K, V> {private final int capacity;private final LinkedHashMap<K, V> cache;private final Lock lock = new ReentrantLock();public LRUCache(int capacity) {this.capacity = capacity;this.cache = new LinkedHashMap<K, V>(capacity + 1, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}};}/*** get* @author senfel* @date 2024/2/26 12:58* @return V */public V get(K key) {lock.lock();try {V value = cache.get(key);if (value != null) {// 触发访问,使得此条目变为最近使用过的cache.remove(key);cache.put(key, value);}return value;} finally {lock.unlock();}}/*** get* @author senfel* @date 2024/2/26 12:58* @return void*/public void put(K key, V value) {lock.lock();try {// 首先尝试移除旧的键值对,即使它可能不存在cache.remove(key);cache.put(key, value);} finally {lock.unlock();}}
}

写在最后

在这个高级版本的LRU缓存实现中,我们使用了LinkedHashMap作为基础数据结构,并通过重写removeEldestEntry方法实现了缓存满时自动淘汰最久未使用的元素。同时,为了保证在多线程环境下的线程安全性,我们在get和put方法上加了synchronized关键字或者使用了ReentrantLock来确保同一时间只有一个线程能执行修改缓存的操作。在get方法中,我们还额外做了一步,即在获取到key对应值后重新插入以更新其为最近使用的元素。

这篇关于设计并实现一个并发安全的LRU(Least Recently Used,最近最少使用)缓存结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/750526

相关文章

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)

《使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)》PPT是一种高效的信息展示工具,广泛应用于教育、商务和设计等多个领域,PPT文档中常常包含丰富的图片内容,这些图片不仅提升了... 目录一、引言二、环境与工具三、python 提取PPT背景图片3.1 提取幻灯片背景图片3.2 提取

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl