【图解数据结构与算法】LRU缓存淘汰算法面试时到底该怎么写(下)

简介: 链表实现的LRU缓存淘汰算法的时间复杂度是O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到O(1)。 Redis的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。Redis有序集合不仅使用了跳表,还用到了散列表。 LinkedHashMap也用到了散列表和链表两种数据结构。散列表和链表都是如何组合起来使用的,以及为什么散列表和链表会经常放到一块使用。

Java LinkedHashMap

HashMap就是通过hash表这种数据结构实现的。而LinkedHashMap并不仅仅是通过链表法解决散列冲突的。

HashMap<Integer, Integer> m = new LinkedHashMap<>();
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}

上面的代码会按照数据插入的顺序依次来打印。而hash表数据经过hash函数扰乱后是无规律存储的,它是如何实现按照数据的插入顺序来遍历打印的呢?

就是通过hash表和链表组合实现,可支持:

  • 按照插入顺序遍历数据
  • 按访问顺序遍历数据

你可以看下面这段代码:

image.png

打印结果

image.png

每次调用 LinkedHashMap#put()添加数据时,都会将数据添加到链尾,前四个操作完成后,链表数据如下:

image.png

第二次将键值为3的数据放入到LinkedHashMap时,会先查找该K是否已有,然后,再将已经存在的(3,11)删除,并将新的(3,26)放到链尾。

这个时候链表中的数据就是下面这样:

image.png

访问K=5数据时,将被访问到的数据移动到链尾。此时,链表数据如下:

image.png

可见,按访问时间排序的LinkedHashMap本身就是个支持LRU缓存淘汰策略的缓存系统。

LinkedHashMap中的“Linked”实际上是指的是双向链表,并非指用链表法解决哈希冲突。

为什么hash表和链表经常一块使用?

hash表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但hash表中的数据都是通过hash函数打乱之后无规律存储的。也就说,它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历。


因为散列表是动态数据结构,不停地有数据的插入、删除,所以每当我们希望按顺序遍历散列表中的数据的时候,都需要先排序,那效率势必会很低。为了解决这个问题,我们将散列表和链表(或者跳表)结合在一起使用。

手写LRU

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;
    // 这里就是传递进来最多能缓存多少数据
    public LRUCache(int cacheSize) {
        //  true指linkedhashmap将元素按访问顺序排序
        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
        CACHE_SIZE = cacheSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // 当KV数据量大于指定缓存个数时,就自动删除最老数据
        return size() > CACHE_SIZE;
    }
}

FAQ

本文的散列表和链表结合使用的例子用的都是双向链表。如果把双向链表改成单链表,还能否正常工作呢?

在删除一个元素时,虽然能 O(1) 的找到目标结点,但是要删除该结点需要拿到前一个结点的指针,遍历到前一个结点复杂度会变为 O(N),所以用双链表实现比较合适。(硬要操作的话,单链表也是可以实现 O(1) 时间复杂度删除结点的)。


假设有 10 万名猎头,每个猎头都可以通过做任务(比如发布职位)来积累积分,然后通过积分来下载简历。假设你是猎聘网的一名工程师,如何在内存中存储这 10 万个猎头 ID 和积分信息,让它能够支持这样几个操作:


根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息

查找积分在某个区间的猎头 ID 列表

查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表

以积分排序构建一个跳表,再以猎头 ID 构建一个散列表:

1)ID 在散列表中所以可以 O(1) 查找到这个猎头;

2)积分以跳表存储,跳表支持区间查询;

3)这点根据目前学习的知识暂时无法实现


目录
相关文章
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
194 0
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
4月前
|
缓存 人工智能 算法
lru算法设计与实现
本文详细介绍了LRU(Least Recently Used,最近最少使用)缓存淘汰策略的原理与实现。LRU的核心思想是:越近被访问的数据,未来被再次访问的可能性越大。文章通过Java语言实现了一个支持O(1)时间复杂度操作的LRU缓存
140 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
190 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
198 22
|
5月前
|
缓存 NoSQL 关系型数据库
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
美团面试:MySQL有1000w数据,redis只存20w的数据,如何做 缓存 设计?
|
15天前
|
存储 缓存 NoSQL
Redis专题-实战篇二-商户查询缓存
本文介绍了缓存的基本概念、应用场景及实现方式,涵盖Redis缓存设计、缓存更新策略、缓存穿透问题及其解决方案。重点讲解了缓存空对象与布隆过滤器的使用,并通过代码示例演示了商铺查询的缓存优化实践。
93 1
Redis专题-实战篇二-商户查询缓存
|
5月前
|
缓存 NoSQL Java
Redis+Caffeine构建高性能二级缓存
大家好,我是摘星。今天为大家带来的是Redis+Caffeine构建高性能二级缓存,废话不多说直接开始~
723 0

热门文章

最新文章