源码解析带你了解LinkedHashMap

目录
  • 元素存储关系
  • 继承体系
  • 属性
  • 构造方法
    • 无参
    • 有参
  • 按插入顺序访问
    • newNode
    • linkNodeLast
  • 链表节点的删除
  • LRU(Least recently used,最近最少使用)
    • 栗子
    • 元素被移到队尾

LinkedHashMap维护插入的顺序。

元素存储关系

红黄箭头:元素添加顺序
蓝箭头:单链表各个元素的存储顺序
head:链表头部
tail:链表尾部

继承体系

  • 继承自 HashMap ,因此 HashMap 拥有的荣耀它也都有.

属性

  • 双向链表的头(最老)

  • 双链表的末尾(最小)

  • HashMap.Node的子类:常规 LinkedHashMap 节点,增加了 before 和 after 属性,维护双向链表的结构

此 LinkedHashMap 的迭代排序方法:

  • true: 访问顺序
  • false(默认): 插入顺序

构造方法

构造方法都是先执行父类 HashMap 的构造方法.

无参

  • 构造一个空的维护插入顺序的LinkedHashMap实例,其默认初始容量(16)和负载因子(0.75).

有参

  • 构造一个空的LinkedHashMap实例,可自己指定初始容量,负载因子和排序模式.

  • 构造一个维护插入顺序的LinkedHashMap实例,该实例具有与指定map相同的映射关系,创建的LinkedHashMap实例具有默认的加载因子(0.75)和足以容纳指定map中映射的初始容量.

下面我们开始研究该类的主要特性是如何通过代码实现的.

按插入顺序访问

LinkedHashMap 默认 accessOrder 为 false,提供按照插入顺序的访问,并没有重写父类 HashMap 的 put 方法.但在 HashMap 中,put 的是 HashMap 的 Node 类型节点,LinkedHashMap 的 Entry 与其结构并不同,又是怎样建立起双向链表的呢?下面一起看下 LinkedHashMap 插入相关代码.

忽略未重写的 put=>putValue代码部分,我们直接观察重写的

newNode

  • HashMap

  • LinkedHashMap 重写

控制新增节点追加到链表的尾部,这样每次新节点都追加到尾部,即可保证插入顺序了.
继续研究 linkNodeLast

linkNodeLast

新增节点,并追加到链表的尾部.

`// link at the end of list`

`private` `void` `linkNodeLast(LinkedHashMap.Entry<K,V> p) {`

`LinkedHashMap.Entry<K,V> last = tail;`

`// 新增于尾节点`

`tail = p;`

`// last 为null,说明链表为空`

`if` `(last == ``null``)`

`head = p;`

`// 链表非空,建立新节点和上一个尾节点的前后关系`

`else` `{`

`// 将新节点 p 直接接在链尾`

`p.before = last;`

`last.after = p;`

`}`

`}`

由此得知,通过在 HashMap 基础上新增的头尾节点,节点的 before 和 after 属性,就能实现在每次新增时,把节点直接追加到尾节点,即可达到维护按照插入顺序的链表结构的目的!

  • 图解链表创建步骤

蓝色部分是 HashMap 的方法
橙色部分为 LinkedHashMap 独有方法

注意 LinkedHashMap 虽然也是双向链表,但只提供单向的按插入的顺序从头到尾访问,不及 LinkedList 般可双向无死角访问.

  • LinkedHashMap 通过迭代器访问,而且默认是从头节点开始访问

迭代过程中,不断访问 after 节点即可完成遍历.

1 处进行校验
2 处通过节点的 after 属性,找到后继节点

链表节点的删除

  • HashMap 中保存的允许 LinkedHashMap 后处理的回调

与插入操作一样,LinkedHashMap 删除操作相关的代码也是直接用父类的实现. 在删除节点时,父类不会修复 LinkedHashMap 的双向链表。那么删除及节点后,被删除的节点该如何从双链表中安全移除呢?其实在删除节点后,回调方法 afterNodeRemoval 会被调用。LinkedHashMap 重写了该方法.

`// e 为已经删除的节点`

`void` `afterNodeRemoval(Node<K,V> e) { ``// unlink`

`LinkedHashMap.Entry<K,V> p =`

`(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;`

`// 将 p 节点的前驱后后继引用置 null,辅助 GC`

`p.before = p.after = ``null``;`

`// p.before 为 null,表明 p 是头节点`

`if` `(b == ``null``)`

`head = a;`

`else`

`// 否则将 p 的前驱节点连接到 p 的后继节点`

`b.after = a;`

`// a 为 null,表明 p 是尾节点`

`if` `(a == ``null``)`

`tail = b;`

`else`

`// 否则将 a 的前驱节点连接到 b`

`a.before = b;`

`}`

删除元素的主要流程:

  • 根据 hash 定位到桶位置
  • 遍历链表或调用红黑树相关的删除方法
  • 从 LinkedHashMap 维护的双链表中移除要删除的节点

转存失败重新上传取消

LRU(Least recently used,最近最少使用)

栗子

经常访问的元素会被追加到队尾,这样不经常访问的数据自然就靠近队头,然后可以通过设置删除策略,比如当 Map 元素个数大于多少时,把头节点删除

元素被移到队尾

get 时,元素会被移动到队尾:

`public` `V get(Object key) {`

`Node<K,V> e;`

`// 调用 HashMap  get 方法`

`if` `((e = getNode(hash(key), key)) == ``null``)`

`return` `null``;`

`// 如果设置了 LRU 策略`

`if` `(accessOrder)`

`// 这个方法把当前 key 移动到队尾`

`afterNodeAccess(e);`

`return` `e.value;`

`}`

从上述源码中,可以看到,通过 afterNodeAccess 方法把当前访问节点移动到了队尾,其实不仅仅是 get 方法,执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时,也会这么做,通过不断的把经常访问的节点移动到队尾,那么靠近队头的节点,自然就是很少被访问的元素了。

到此这篇关于源码解析带你了解LinkedHashMap的文章就介绍到这了,更多相关Java LinkedHashMap内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-09-14

Java LinkedHashMap 底层实现原理分析

在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表覆写了部分方法.所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码. 默认情况下,LinkedHashMap的迭代顺序是按照插入节点的顺序.也可以通过改变accessOrder参数的值,使得其遍历顺序按照访问顺序输出. 这里我们只讨论LinkedHashMap和HashMap的不同之处,LinkedHashMap的其他操作和特性具体请参考HashMap 我们先来看下两者的区别:

Java集合系列之LinkedHashMap源码分析

这篇文章我们开始分析LinkedHashMap的源码,LinkedHashMap继承了HashMap,也就是说LinkedHashMap是在HashMap的基础上扩展而来的,因此在看LinkedHashMap源码之前,读者有必要先去了解HashMap的源码,可以查看我上一篇文章的介绍<Java集合系列[3]----HashMap源码分析>.只要深入理解了HashMap的实现原理,回过头来再去看LinkedHashMap,HashSet和LinkedHashSet的源码那都是非常简单的.因此,读

Java源码解析之LinkedHashMap

一.成员变量 先来看看存储元素的结构吧: static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } 这个Entry在HashMap中被引用过,主要是为了能让LinkedHashMap也支持树化.

Java中LinkedHashMap源码解析

概述: LinkedHashMap实现Map继承HashMap,基于Map的哈希表和链该列表实现,具有可预知的迭代顺序. LinedHashMap维护着一个运行于所有条目的双重链表结构,该链表定义了迭代顺序,可以是插入或者访问顺序. LintHashMap的节点对象继承HashMap的节点对象,并增加了前后指针 before after: /** * LinkedHashMap节点对象 */ static class Entry<K,V> extends HashMap.Node<K,V

Java集合框架源码分析之LinkedHashMap详解

LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

java集合类源码分析之Set详解

Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet.值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下: •Set集合中的元素不能重复,即元素唯一 •HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象 •TreeSet按元素的大小存储,所以是有序的,并且不允许null对象 •Set集合没有ge

JAVA 枚举单例模式及源码分析的实例详解

JAVA 枚举单例模式及源码分析的实例详解 单例模式的实现有很多种,网上也分析了如今实现单利模式最好用枚举,好处不外乎三点: 1.线程安全 2.不会因为序列化而产生新实例 3.防止反射攻击但是貌似没有一篇文章解释ENUM单例如何实现了上述三点,请高手解释一下这三点: 关于第一点线程安全,从反编译后的类源码中可以看出也是通过类加载机制保证的,应该是这样吧(解决) 关于第二点序列化问题,有一篇文章说枚举类自己实现了readResolve()方法,所以抗序列化,这个方法是当前类自己实现的(解决) 关于

nginx源码分析线程池详解

nginx源码分析线程池详解 一.前言 nginx是采用多进程模型,master和worker之间主要通过pipe管道的方式进行通信,多进程的优势就在于各个进程互不影响.但是经常会有人问道,nginx为什么不采用多线程模型(这个除了之前一篇文章讲到的情况,别的只有去问作者了,HAHA).其实,nginx代码中提供了一个thread_pool(线程池)的核心模块来处理多任务的.下面就本人对该thread_pool这个模块的理解来跟大家做些分享(文中错误.不足还请大家指出,谢谢) 二.thread_

nginx源码分析configure脚本详解

nginx源码分析--configure脚本 一.前言 在分析源码时,经常可以看到类似 #if (NGX_PCRE) .... #endif 这样的代码段,这样的设计可以在不改动源码的情况下,通过简单的定义宏的方式来实现功能的打开与关闭,但是在nginx/src目录下始终没有找到宏 NGX_PCRE 对应的 #define 语句. 在之前介绍event模块的时候,讲到init_cycle函数中对cycle进行了初始化,其中很重要一步操作就是讲包含所有module信息的数组拷贝到这个cycle对应

jQuery源码分析之Callbacks详解

代码的本质突出顺序.有序这一概念,尤其在javascript--毕竟javascript是单线程引擎. javascript拥有函数式编程的特性,而又因为javascript单线程引擎,我们的函数总是需要有序的执行.优秀代码常常 把函数切割成各自的模块,然后在某一特定条件下执行,既然这些函数是有序的执行,那么我们为什么不编写一个统一管理的对象,来帮助我们管理这些函数--于是,Callbacks(回调函数)诞生. 什么是Callbacks javascript中充斥着函数编程,例如最简单的wind

Django restframework 源码分析之认证详解

前言 最近学习了 django 的一个 restframework 框架,对于里面的执行流程产生了兴趣,经过昨天一晚上初步搞清楚了执行流程(部分方法还不太清楚),于是想详细的总结一下当来一个请求时,在该框架里面是如何执行的? 启动项目时 昨天在调试django时,发现在 APIView 中打的断点没有断下来,而是打在 View 中的断点断下来了,调试了很多次,最后发现,在 django 项目启动时,会首先加载 urls 中的文件,执行 views 中类的 as_view方法,其实是继承自 API

通过JDK源码分析关闭钩子详解

关闭钩子 用户关闭关闭程序,需要做一些善后的清理工作,但问题是,某些用户不会按照推荐的方法关闭应用程序,肯能导致善后工作无法进行.像tomcat调用server的start方法启动容器,然后会逐级调用start.当发出关闭命令是会启动关闭功能,但是关闭可能会有一些意外产生,导致应用程序没有进入到我们制定的关闭方法去.如何解决这个问题呢,使得即使有意外也能正常进入关闭流程. 好在java提供了一种优雅的方式去解决这种问题.使得关闭的善后处理的代码能执行.java的关闭钩子能确保总是执行,无论用户如

Java源码解析之TypeVariable详解

TypeVariable,类型变量,描述类型,表示泛指任意或相关一类类型,也可以说狭义上的泛型(泛指某一类类型),一般用大写字母作为变量,比如K.V.E等. 源码 public interface TypeVariable<D extends GenericDeclaration> extends Type { //获得泛型的上限,若未明确声明上边界则默认为Object Type[] getBounds(); //获取声明该类型变量实体(即获得类.方法或构造器名) D getGenericDe

Java源码解析之GenericDeclaration详解

学习别人实现某个功能的设计思路,来提高自己的编程水平.话不多说,下面进入正题. GenericDeclaration 可以声明类型变量的实体的公共接口,也就是说,只有实现了该接口才能在对应的实体上声明(定义)类型变量,这些实体目前只有三个:Class(类).Construstor(构造器).Method(方法)(详见:Java源码解析之TypeVariable详解 源码 public interface GenericDeclaration { //获得声明列表上的类型变量数组 public T