当前位置: 首页 > news >正文

Java的LinkedHashMap 源码解析

LinkedHashMap 是 Java 中的一种有序 Map,它扩展了 HashMap,提供了有序的元素存储方式。在 LinkedHashMap 中,元素的有序性可以按照插入顺序或访问顺序来维护,而这个有序性是通过维护一个双向链表来实现的,这也是实现 LRU Cache 功能的基础。在接下来的源码解析中,我们将深入探讨 LinkedHashMap 的实现。

在这里插入图片描述

主要结论

在开始分析源码之前,让我们首先总结一些关键结论:

  1. LinkedHashMap 继承了 HashMap,因此它的底层数据结构与 HashMap 相同,都是由数组、链表或红黑树组成,同时也使用相同的扩容机制。

    /*** 用指定的初始容量、加载因子和排序模式构造一个空的LinkedHashMap实例。** @param initialCapacity 初始容量* @param loadFactor      加载因子* @param accessOrder     排序模式 - <tt>true</tt> 表示按访问顺序,<tt>false</tt> 表示按插入顺序* @throws IllegalArgumentException 如果初始容量为负数或加载因子为非正数*/
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {// 调用 HashMap 的构造方法,继承了 HashMap 的底层数据结构和扩容机制super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
    }
    
  2. LinkedHashMap 使用双向链表来维护数据的顺序,与 HashMap 的拉链式存储方式不同。

    /** 实现说明。此类的先前版本在内部结构上略有不同。由于超类 HashMap 现在对一些节点使用树结构,类 LinkedHashMap.Entry 现在被视为中介节点类,也可以转换为树形结构。在当前上下文中,此类的名称 LinkedHashMap.Entry 在几个方面都有点令人困惑,但不能更改。否则,即使它不被导出到此包外,已知一些现有源代码依赖于调用 removeEldestEntry 时的符号解析特例规则,以抑制由于模糊的用法而导致的编译错误。因此,我们保留名称以保持编译性不变。** 节点类的更改还需要使用两个字段(head、tail)而不是指向头节点的指针来维护双向链接的前后列表。该类以前也使用了不同风格的回调方法来进行访问、插入和删除。*//*** 用于常规 LinkedHashMap 条目的 HashMap.Node 子类。*/
    static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, value, Node<K,V> next) {super(hash, key, value, next);}
    }
    
  3. LinkedHashMap 存储顺序与添加顺序一致,但也可以通过 accessOrder 参数决定是否在访问元素时移动元素,以实现 LRU 缓存功能。

    /*** 在删除元素之后,将元素从双向链表中删除*/
    void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
    }/*** 在访问元素之后,将该元素放到双向链表的尾巴处*/
    void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
    }
    

内部结构

LinkedHashMap 内部类 Entry 继承自 HashMap 的 Node,同时增加了 “前继节点” 和 “后继节点” 来支持双向链表的特性。此外,LinkedHashMap 中还有两个重要的成员变量:

  • head:记录 LinkedHashMap 的头节点。
  • tail:记录 LinkedHashMap 的尾节点。
  • accessOrder:表示是否根据访问顺序进行排序,如果 accessOrder 为 true,LinkedHashMap 会在元素被访问时将其移至链表末尾,实现 LRU 缓存。

内部方法

LinkedHashMap 定义了一些私有的内部方法,用于操作双向链表:

  • linkNodeLast(LinkedHashMap.Entry<K,V> p):将元素连接到链表尾部。

    /*** 将元素连接到链表尾部。** @param p 要连接到链表尾部的元素*/
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}
    }
    
  • transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst):将一个节点的前继节点和后继节点链接到另一个节点。

    /*** 将一个节点的前继节点和后继节点链接到另一个节点。** @param src 要转移链接的源节点* @param dst 目标节点*/
    private void transferLinks(LinkedHashMap.Entry<K,V> src,LinkedHashMap.Entry<K,V> dst) {LinkedHashMap.Entry<K,V> b = dst.before = src.before;LinkedHashMap.Entry<K,V> a = dst.after = src.after;if (b == null)head = dst;elseb.after = dst;if (a == null)tail = dst;elsea.before = dst;
    }
    
  • afterNodeRemoval(Node<K,V> e):在删除元素后,将元素从双向链表中删除。

    /*** 在删除元素后,将元素从双向链表中删除。** @param e 要删除的元素*/
    void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
    }
    
  • afterNodeInsertion(boolean evict):在插入元素后,可能删除最老的元素。

    /*** 在插入元素后,可能删除最老的元素。** @param evict 如果为 true,可能会删除最老的元素*/
    void afterNodeInsertion(boolean evict) { // 可能删除最老的元素LinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
    }
    
  • afterNodeAccess(Node<K,V> e):在访问元素后,将元素放到链表的尾部。

    /*** 在访问元素后,将元素放到链表的尾部。** @param e 要移动的元素*/
    void afterNodeAccess(Node<K,V> e) { // 将节点移动到最后LinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) { // 如果 accessOrder 与 (last = tail) != e 为 trueLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
    }
    

构造方法

LinkedHashMap 提供了多个构造方法,包括:

  • LinkedHashMap(int initialCapacity, float loadFactor):指定初始容量和加载因子的构造方法。

    /*** 指定初始容量和加载因子的构造方法。** @param initialCapacity 初始容量* @param loadFactor 加载因子*/
    public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;
    }
    
  • LinkedHashMap(int initialCapacity):指定初始容量的构造方法。

    /*** 指定初始容量的构造方法。** @param initialCapacity 初始容量*/
    public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;
    }
    
  • LinkedHashMap():默认构造方法。

    /*** 默认构造方法。*/
    public LinkedHashMap() {super();accessOrder = false;
    }
    
  • LinkedHashMap(Map<? extends K, ? extends V> m):使用现有映射初始化构造方法。

    /*** 使用现有映射初始化构造方法。** @param m 要使用的映射*/
    public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);
    }
    
  • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder):可以设置 accessOrder 参数以决定是否按照访问顺序排序。

    /*** 可以设置 accessOrder 参数以决定是否按照访问顺序排序。** @param initialCapacity 初始容量* @param loadFactor 加载因子* @param accessOrder 如果为 true,则按照访问顺序排序;否则按照插入顺序排序*/
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
    }
    

LinkedHashMap 的源码解析包括实现 newNodereplacementNodenewTreeNodereplacementTreeNode 等节点插入和替换的方法,以及实现 containsValuegetgetOrDefaultkeySetentrySet 等其他操作。这些方法负责在 LinkedHashMap 中维护元素的顺序和实现 LRU 缓存功能。

总结

LinkedHashMap 是一个有序的 Map,它维护元素的有序性,可以按照插入顺序或访问顺序排列元素。这个有序性是通过维护一个双向链表来实现的。另外,LinkedHashMap 提供了 accessOrder 参数来决定是否在访问元素时移动元素,以实现 LRU 缓存功能。这使得 LinkedHashMap 成为一个非常有用的数据结构,适用于需要有序性和缓存功能的场景。

相关文章:

Java的LinkedHashMap 源码解析

LinkedHashMap 是 Java 中的一种有序 Map&#xff0c;它扩展了 HashMap&#xff0c;提供了有序的元素存储方式。在 LinkedHashMap 中&#xff0c;元素的有序性可以按照插入顺序或访问顺序来维护&#xff0c;而这个有序性是通过维护一个双向链表来实现的&#xff0c;这也是实现 …...

Linux系统及常用指令

目录 1、什么是Linux系统 2、为什么要用Linux系统 3、Linux系统的种类 4、如何安装Linux系统 5、常见的适配器种类 6、学习第一个Linux指令 7、安装ssh客户端软件 8、Linux系统的目录结构 9、Linux的常用命令 9.1 目录切换命令 9.2 查看目录下的内容 9.3 查看当前…...

Mac Electron 应用如何进行签名(signature)和公证(notarization)?

最近很多客户反映&#xff0c;从官网下载的Mac Electron应用打不开&#xff0c;直接报病毒&#xff0c;类似于这种&#xff1a; 这是因为在MacOS 10.14.5之后&#xff0c;如果应用没有在苹果官方平台进行公证notarization(我们可以理解为安装包需要审核&#xff0c;来判断是否存…...

【C++ | 抽象类】纯虚函数 和 抽象基类,为什么需要抽象基类

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

DP(7) | 打家劫舍① | Java | LeetCode 198, 213, 337 做题总结(未完)

打家劫舍问题 来源于代码随想录&#xff1a;https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#%E6%80%9D%E8%B7%AF ① 确定dp数组&#xff08;dp table&#xff09;以及下标的含义 dp[i]&#xff1a;考虑下标i&#xff08;包括i&#xff09;以内的房…...

人工智能算法工程师(中级)课程17-模型的量化与部署之剪枝技巧与代码详解

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能算法工程师(中级)课程17-模型的量化与部署之剪枝技巧与代码详解。模型剪枝是深度学习领域中一项关键的技术&#xff0c;旨在减少神经网络中的冗余权重&#xff0c;从而降低计算成本和内存占用&#xff0c;同…...

JavaScript 实例:掌握编程技巧

JavaScript 实例:掌握编程技巧 JavaScript 是一种广泛使用的编程语言,它为网页添加交互性,是现代网络开发的重要组成部分。本文将通过一系列实例,帮助您更好地理解和掌握 JavaScript 的核心概念和编程技巧。 基础实例:变量和数据类型 首先,让我们从最基础的开始。Java…...

自己做小项目时,配置的Maven需要用阿里云私服加速Jar包的下载

在我的IDEA中&#xff0c;maven配置在了这个地址&#xff0c;然后我需要去这个地址下找到settings.xml的maven配置文件来配置以下的阿里云私服地址来加速jar包的下载&#xff01;【不然就是下N年很慢&#xff01;】...

Linux笔记之time命令测量命令的执行时间

Linux笔记之time命令测量命令的执行时间 在Linux中&#xff0c;time命令用于测量命令的执行时间。这对于分析和优化脚本或程序的性能非常有用。time命令会显示三个主要时间指标&#xff1a; real: 从命令开始到结束的实际时间&#xff08;也称为挂钟时间&#xff09;。user: …...

《基于 CDC、Spark Streaming、Kafka 实现患者指标采集》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

重要的单元测试

&#x1f47d;System.out.println(“&#x1f44b;&#x1f3fc;嗨&#xff0c;大家好&#xff0c;我是代码不会敲的小符&#xff0c;目前工作于上海某电商服务公司…”); &#x1f4da;System.out.println(“&#x1f388;如果文章中有错误的地方&#xff0c;恳请大家指正&…...

什么是diff算法?

Diff算法&#xff0c;全称为Difference算法&#xff0c;是一种用于比较和查找两个对象&#xff08;如文本、源代码、数据结构或任何形式的字符串&#xff09;之间差异的算法。它在多个领域有着广泛的应用&#xff0c;包括但不限于前端开发、版本控制系统、协同编辑工具等。以下…...

BUUCTF逆向wp [MRCTF2020]Transform

第一步 查壳。该题为64位。 第二步 进入主函数&#xff0c;跟进dword_40F040,它应该与关键字符串有关 分析一下&#xff1a; 初始化和输入 sub_402230(argc, argv, envp); 这行可能是一个初始化函数&#xff0c;用于设置程序环境或处理命令行参数。具体功能不明&#xff0c…...

前端下载文件流 出现乱码 解决方案

1. 后端返回文件格式不是 utf-8 解决方案&#xff1a;后端加 2. 若添加 utf-8 后依旧乱码 请求配置中添加 responseType: arraybuffer, export function downMode() {return http.request({url: baseUrl downTemplate,method: get,responseType: arraybuffer,}); }下载 con…...

Linux/Windows 系统分区

1. Windows 系统 1.1 系统分区 系统分区也叫做磁盘分区&#xff0c;即分盘&#xff1b; 举个例子&#xff0c;好比家里有一个大柜子&#xff0c;把衣服&#xff0c;鞋子&#xff0c;袜子都放在里面&#xff0c;由于没有隔断&#xff0c;找的时候非常麻烦&#xff0c;找是能找…...

C/C++ xml库

文章目录 一、介绍1.1 xml 介绍1.2 xml 标准1.3 xml 教程1.4 xml 构成 二、C/C xml 库选型2.1 选型范围2.2 RapidXML2.3 tinyxml22.4 pugixml2.5 libxml 五、性能比较5.1 C xml 相关的操作有哪些5.2 rapidxml、Pugixml、TinyXML2 文件读取性能比较 六、其他问题6.1 version和 e…...

UniVue@v1.5.0版本发布:里程碑版本

前言 以后使用UniVue都推荐使用1.5.0以后的版本&#xff0c;这个版本之后&#xff0c;更新的速度将会放缓。 希望这个框架能够切实的帮助大家更好的开发游戏&#xff0c;做出一款好游戏&#xff01;本开源项目采用的开源协议为MIT协议&#xff0c;完全开源化&#xff0c;以后也…...

在 Windows 上开发.NET MAUI 应用_2.生成你的第一个应用

先决条件 Visual Studio 2022 17.8 或更高版本&#xff0c;并安装了 .NET Multi-platform App UI 工作负载。 可参考上一篇文章&#xff1a;http://t.csdnimg.cn/n38Yy 创建应用 1.启动 Visual Studio 2022。 在开始窗口中&#xff0c;单击“创建新项目”以创建新项目&#…...

配置SMTP服务器的要点是什么?有哪些限制?

配置SMTP服务器安全性如何保障&#xff1f;如何高效配置服务器&#xff1f; SMTP作为电子邮件发送的核心协议&#xff0c;其配置对于确保邮件的成功传递和安全至关重要。AokSend将详细介绍配置SMTP服务器的关键要点&#xff0c;帮助读者建立一个高效、安全的邮件发送系统。 配…...

图形渲染基础-Unity渲染管线介绍

Unity中的渲染管线渲染场景主要分为三个阶段 剔除&#xff08;Culling&#xff09; 剔除摄像机不可见对象&#xff08;视锥体剔除Frustum Culling&#xff09;和被遮挡对象&#xff08;遮挡剔除Occlusion Culling&#xff09;。 渲染&#xff08;Rendering&#xff09; 将可见…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...