【图解数据结构与算法】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)这点根据目前学习的知识暂时无法实现


目录
相关文章
|
15天前
|
缓存 安全 算法
Java面试题:如何通过JVM参数调整GC行为以优化应用性能?如何使用synchronized和volatile关键字解决并发问题?如何使用ConcurrentHashMap实现线程安全的缓存?
Java面试题:如何通过JVM参数调整GC行为以优化应用性能?如何使用synchronized和volatile关键字解决并发问题?如何使用ConcurrentHashMap实现线程安全的缓存?
12 0
|
5天前
|
SQL 缓存 Java
【面试官】Mybatis缓存有什么问题吗?
面试官:你说下对MyBatis的理解?面试官:那SqlSession知道吧?面试官:Mybatis的缓存有哪几种?面试官:那Mybatis缓存有什么问题吗?面试官:Mybatis分页插件是怎么
【面试官】Mybatis缓存有什么问题吗?
|
9天前
|
canal 缓存 NoSQL
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;先删除缓存还是先修改数据库,双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
Redis常见面试题(一):Redis使用场景,缓存、分布式锁;缓存穿透、缓存击穿、缓存雪崩;双写一致,Canal,Redis持久化,数据过期策略,数据淘汰策略
|
2天前
|
canal 消息中间件 缓存
面试题:如何解决缓存和数据库的一致性问题?
面试题:如何解决缓存和数据库的一致性问题?
13 1
|
29天前
|
存储 缓存 NoSQL
架构面试题汇总:缓存(2024版)
架构面试题汇总:缓存(2024版)
|
15天前
|
存储 缓存 算法
Java面试题:给出代码优化的常见策略,如减少对象创建、使用缓存等。
Java面试题:给出代码优化的常见策略,如减少对象创建、使用缓存等。
19 0
|
15天前
|
设计模式 存储 缓存
Java面试题:结合设计模式与并发工具包实现高效缓存;多线程与内存管理优化实践;并发框架与设计模式在复杂系统中的应用
Java面试题:结合设计模式与并发工具包实现高效缓存;多线程与内存管理优化实践;并发框架与设计模式在复杂系统中的应用
18 0
|
15天前
|
设计模式 存储 缓存
Java面试题:结合单例模式与Java内存模型,设计一个线程安全的单例类?使用内存屏障与Java并发工具类,实现一个高效的并发缓存系统?结合观察者模式与Java并发框架,设计一个可扩展的事件处理系统
Java面试题:结合单例模式与Java内存模型,设计一个线程安全的单例类?使用内存屏障与Java并发工具类,实现一个高效的并发缓存系统?结合观察者模式与Java并发框架,设计一个可扩展的事件处理系统
16 0
|
23天前
|
缓存 算法 前端开发
前端 JS 经典:LRU 缓存算法
前端 JS 经典:LRU 缓存算法
15 0
|
24天前
|
缓存 编解码 安全
Android经典面试题之Glide的缓存大揭秘
Glide缓存机制包括内存和硬盘缓存。内存缓存使用弱引用的ActiveResources和LRU策略,硬盘缓存利用DiskLruCache。Engine.load方法首先尝试从内存和弱引用池加载,然后从LRU缓存中加载图片,增加引用计数并移出LRU。若缓存未命中,启动新任务或加入现有任务。内存大小根据设备内存动态计算,限制在0.4以下。DiskLruCache使用自定义读写锁,保证并发安全,写操作通过锁池管理,确保高效。
16 0