首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

LinkedHashMap原理详解—从LRU缓存机制说起

编程知识
2024年09月12日 19:33

写在前面

从一道Leetcode题目说起

首先,来看一下Leetcode里面的一道经典题目:146.LRU缓存机制,题目描述如下:

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。

分析

要让 LRU 的 putget 方法的时间复杂度为 O(1),可以总结出 LRU 这个数据结构必要的条件:

  1. 显然 LRU 中的元素必须有时序,以区分最近使用的和久未使用的数据,当容量满了之后要删除最久未使用的那个元素腾位置。
  2. 要在 LRU 中快速找某个 key 是否已存在并得到对应的 val
  3. 每次访问 LRU 中的某个 key,需要将这个元素变为最近使用的,也就是说 LRU 要支持在任意位置快速插入和删除元素。

那么,什么数据结构同时符合上述条件呢?哈希表查找快,但是数据无固定顺序;链表有顺序之分,插入删除快,但是查找慢。所以结合一下,形成一种新的数据结构:哈希链表 LinkedHashMap

LRU 缓存算法的核心数据结构就是哈希链表,双向链表和哈希表的结合体。这个数据结构长这样:

借助这个结构,逐一分析上面的 3 个条件:

  1. 如果我们每次默认从链表尾部添加元素,那么显然越靠尾部的元素就是最近使用的,越靠头部的元素就是最久未使用的。
  2. 对于某一个 key,我们可以通过哈希表快速定位到链表中的节点,从而取得对应 val
  3. 链表显然是支持在任意位置快速插入和删除的,改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素,而这里借助哈希表,可以通过 key 快速映射到任意一个链表节点,然后进行插入和删除。

put方法流程图:

代码实现

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key,重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

LinkedHashMap介绍

LinkedHashSetLinkedHashMap其实也是一回事。LinkedHashSetLinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)

LinkedHashMap实现了Map接口,即允许放入key为null的元素,也允许插入value为null的元素。从名字上可以看出该容器是linked listHashMap的混合体,也就是说它同时满足HashMaplinked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap

事实上LinkedHashMapHashMap的直接子类,二者唯一的区别是LinkedHashMap在HashMap的基础上,采用双向链表(doubly-linked list)的形式将所有entry连接起来,这样的好处:

  • 可以保证元素的迭代顺序跟插入顺序相同。跟HashMap相比,多了header指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry的插入顺序

  • 迭代LinkedHashMap时不需要像HashMap那样遍历整个table,而只需要直接遍历header指向的双向链表即可,也就是说LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。这点与HashMap是一样的

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

注意,这里的插入有两重含义:

  • 从table的角度看,新的entry需要插入到对应的bucket里,当有哈希冲突时,采用头插法将新的entry插入到冲突链表的头部。
  • 从header的角度看,新的entry需要插入到双向链表的尾部。

addEntry()代码如下:

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面,这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

注意,这里的删除也有两重含义:

  • 从table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。

  • 从header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

removeEntryForKey()对应的代码如下:

// LinkedHashMap.removeEntryForKey(),删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

LinkedHashSet

LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

关于作者

来自一线程序员Seven的探索与实践,持续学习迭代中~

本文已收录于我的个人博客:https://www.seven97.top

公众号:seven97,欢迎关注~

From:https://www.cnblogs.com/seven97-top/p/18411019
本文地址: http://www.shuzixingkong.net/article/1959
0评论
提交 加载更多评论
其他文章 搭建ipv6并发代理池
声明 本文章中所有内容仅供学习交流,抓包内容、敏感网址、数据接口均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关,若有侵权,请联系我立即删除! 学习目标 ounter(lineipv6代理池学习 前置环境配置 要求linux系统。我是pve下的ubuntugolang的
搭建ipv6并发代理池 搭建ipv6并发代理池 搭建ipv6并发代理池
Java怎么把多个对象的list的数据合并
1.示例一:创建几个包含Person对象的List,并将它们合并成一个新的List 在Java中,将多个对象的List合并通常涉及到遍历这些List并将它们的元素添加到一个新的List中。这里,我将给出一个详细的代码示例,该示例将展示如何将多个包含相同类型对象的List合并成一个List。 假设我们
JAVA基础之5-函数式接口的实现
之所以单独把这个列出来,是因为本人被一个源码给震撼了。 所以,本人目的是看看这个震撼实现,并模仿,最后把常规的实现也贴上,让读者可以看到相对完整的实现 注:本文代码基于JDK17 一、让人震撼的代码 Collectors.toList() public static &lt;T&gt; Collec
JAVA基础之5-函数式接口的实现
41岁的大龄程序员,苟着苟着,要为以后做打算了
最近看到 薰衣草写的《写在临近40岁的年龄》 多少有点感慨,直到看到初九写的《40岁大龄失业程序猿,未来该何去何从》 ,有点绷不住了,如果说薰衣草写的有点抒情,离心里的距离还有点远,而初九的情况简直像照进现实的镜子,映射出未来可能遇到的困境。 许多人在想:“活人难道真会被尿憋死?”觉得桥到床头自然直
Qml 实现仿前端的 Notification (悬浮出现页面上的通知消息)
在前端中一般称它为 Notification 或 Message,但本质是一种东西,即:悬浮弹出式的消息提醒框。 这种组件一般具有以下特点: 1、全局/局部显示:它不依赖于具体的页面元素,可以在整个页面的任意位置显示。 2、自动消失:默认情况下,消息会在一定时间后自动消失,也可以设置为不自动消失。
Qml 实现仿前端的 Notification (悬浮出现页面上的通知消息) Qml 实现仿前端的 Notification (悬浮出现页面上的通知消息) Qml 实现仿前端的 Notification (悬浮出现页面上的通知消息)
Vert.x HttpClient调用后端服务时使用Idle Timeout和KeepAlive Timeout的行为分析
其实网上有大量讨论HTTP长连接的文章,而且Idle Timeout和KeepAlive Timeout都是HTTP协议上的事情,跟Vert.x本身没有太大关系,只不过最近在项目上遇到了一些问题,用到了Vert.x的HttpClient,就干脆总结一下,留给自己今后做参考。 在使用Vert.x的Ht
Vert.x HttpClient调用后端服务时使用Idle Timeout和KeepAlive Timeout的行为分析 Vert.x HttpClient调用后端服务时使用Idle Timeout和KeepAlive Timeout的行为分析 Vert.x HttpClient调用后端服务时使用Idle Timeout和KeepAlive Timeout的行为分析
DECL: 针对噪声时间序列的去噪感知对比学习《Denoising-Aware Contrastive Learning for Noisy Time Series》(时间序列、对比学习、去噪)
今天是2024年9月12日,组会摸鱼,很久没看论文了,在摸鱼看代码,最近IJCAI 2024出来了,找了几篇论文看,首先这是第一篇。 论文:Denoising-Aware Contrastive Learning for Noisy Time Series 或者是:Denoising-Aware C
Go日志管理库zap
一、zap介绍 在许多Go语言项目中,我们需要一个好的日志记录器能够提供下面这些功能: 1.能够将事件记录到文件中,而不是应用程序控制台。 2.日志切割-能够根据文件大小、时间或间隔等来切割日志文件。 3.支持不同的日志级别。例如INFO,DEBUG,ERROR等。 4.能够打印基本信息,如调用文件
Go日志管理库zap Go日志管理库zap Go日志管理库zap