首页 / Java / 浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存

LRU:Least Recently Used最近最少使用,…

LRU:Least Recently Used最近最少使用,当缓存容量不足时,先淘汰最近最少使用的数据。就像JVM垃圾回收一样,希望将存活的对象移动到内存的一端,然后清除其余空间。

缓存基本操作就是读、写、淘汰删除。

读操作时间复杂度为O(1)的那就是hash操作了,可以使用HashMap索引 key。

写操作时间复杂度为O(1),使用链表结构,在链表的一端插入节点,是可以完成O(1)操作,但是为了配合读,还要再次将节点放入HashMap中,put操作最优是O(1),最差是O(n)。

不少童鞋就有疑问了,写入时又使用map进行了put操作,为何缓存不直接使用map?没错,首先使用map存储了节点数据就是采用空间换时间,但是淘汰删除不好处理,使用map如何去记录最近最少使用(涉及到时间、频次问题)。so,使用链表可以将活跃节点移动到链表的一端,淘汰时直接从另一端进行删除。

这里使用链表,及HashMap完成了基于LRU的缓存,其中HashMap主要用来快速索引key,链表用来完成LRU机制。当然尚有许多不足,包括缓存移除remove,缓存ttl,线程安全等。

到此这篇关于浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存的文章就介绍到这了,更多相关Java基于LRU时间复杂度为O(1)的缓存内容请搜索我是攻城狮以前的文章或继续浏览下面的相关文章希望大家以后多多支持我是攻城狮!

本文来自网络,不代表我是攻城狮立场,转载请注明出处:https://www.54gcs.cn/programming/java/88962.html

helwo作者

上一篇
下一篇

为您推荐

发表评论

联系我们

联系我们

在线咨询: QQ交谈

邮箱: web@5vo.cn

工作时间:周一至周五,9:00-17:30,节假日休息
关注微信
微信扫一扫关注我们

微信扫一扫关注我们

手机访问
手机扫一扫打开网站

手机扫一扫打开网站

返回顶部
跳至工具栏