史上最全的Java容器集合之LinkedHashMap(源码解读)

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 前言文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820…种一棵树最好的时间是十年前,其次是现在

前言


文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820…

种一棵树最好的时间是十年前,其次是现在

絮叨


Map家族最后一讲了,前面已经讲了最常用的HashMap,讲了线程安全的ConcurrentHashMap,今年就来看看有序的LinkedHashMap

🔥史上最全的Java容器集合之入门

🔥史上最全的Java容器集合之基础数据结构(手撕链表)

🔥史上最全的Java容器集合之ArrayList(源码解读)

🔥史上最全的Java容器集合之Vector和LinkedList(源码解读)

🔥史上最全的Java容器集合之equals 和 hashCode

🔥史上最全的Java容器集合之HashMap(源码解读)

🔥史上最全的Java容器集合之ConcurrentHashMap(源码解读)


概述


LinkedHashMap是HashMap的子类,它的大部分实现与HashMap相同,两者最大的区别在于,HashMap的对哈希表进行迭代时是无序的,而 LinkedHashMap对哈希表迭代是有序的,LinkedHashMap默认的规则是,迭代输出的结果保持和插入key-value pair的顺序一致(当然具体迭代规则可以修改)。LinkedHashMap除了像HashMap一样用数组、单链表和红黑树来组织数据外,还额外维护了一个 双向链表,每次向linkedHashMap插入键值对,除了将其插入到哈希表的对应位置之外,还要将其插入到双向循环链表的尾部。

下面是它的数据结构:


我们可以看出它是由 数组 + 一个单项链表+一个双向链表组成。在原HashMap的数据结构基础上加一个双向链表


LinkedHashMap


继承结构


LinkedHashMap也就是继承HashMap,所以HashMap大都方法,它是可以直接使用的。


顶部的注释总结一下:

  • 底层是散列表和双向链表
  • 允许为null,不同步
  • 插入的顺序是有序的(底层链表致使有序)
  • 装载因子和初始容量对LinkedHashMap影响是很大的~

基本属性


//双向链表的头节点
    transient LinkedHashMap.Entry<K,V> head;
     //双向链表的尾节点
    transient LinkedHashMap.Entry<K,V> tail;
   //排序的规则,false按插入顺序排序,true访问顺序排序 
    final boolean accessOrder;
    //所以说accessOrder的作用就是控制访问顺序,设置为true后每次访问一个元素,就将该元素所在的Node变成最后一个节点,
    改变该元素在LinkedHashMap中的存储顺序。
复制代码


构造方法

//LinkedHashMap的构造方法,都是通过调用父类的构造方法来实现,大部分accessOrder默认为false
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
复制代码


上面是LinkedHashMap的构造方法,通过传入初始化参数和代码看出,LinkedHashMap的构造方法和父类的构造方法,是一一对应的。也是通过super()关键字来调用父类的构造方法来进行初始化,唯一的不同是最后一个构造方法,提供了AccessOrder参数,用来指定LinkedHashMap的排序方式,accessOrder =false -> 插入顺序进行排序 , accessOrder = true -> 访问顺序进行排序。


Entry定义

这个比较重要

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    //定义Entry类型的两个变量,或者称之为前后的两个指针    
    Entry<K,V> before, after;
    //构造方法与HashMap的没有区别,也是调用父类的Entry构造方法
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
    }
    //删除
    private void remove() {
        before.after = after;
        after.before = before;
    }
    //插入节点到指定的节点之前
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }
    //方法重写,HashMap中为空
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }
    //方法重写 ,HashMap中方法为空
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}
复制代码


到这里已经可以知道,相对比HashMap,LinkedHashMap内部不光是使用HashMap中的哈希表来存储Entry对象,还另外维护了一个LinkedHashMapEntry,这些LinkedHashMapEntry内部又保存了前驱跟后继的引用,可以确定这是个双向链表。而这个LinkedHashMapEntry提供了对象的增加删除方法都是去更改节点的前驱后继指向。


put()方法

LinkedHashMap并没有重写父类的put()方法,说明调用put方法时实际上调用的是父类的put方法。HashMap的put这里就不多说了中有这样一个方法


LinkedHashMap 重写了2个方法

ode<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        //用临时变量last记录尾节点tail
        LinkedHashMap.Entry<K,V> last = tail;
        //将尾节点设为当前插入的节点p
        tail = p;
        //如果原先尾节点为null,表示当前链表为空
        if (last == null)
            //头结点也为当前插入节点
            head = p;
        else {
            //原始链表不为空,那么将当前节点的上节点指向原始尾节点
            p.before = last;
            //原始尾节点的下一个节点指向当前插入节点
            last.after = p;
        }
    }
复制代码


//把当前节点放到双向链表的尾部
 2     void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
 3         LinkedHashMap.Entry<K,V> last;
 4         //当 accessOrder = true 并且当前节点不等于尾节点tail。这里将last节点赋值为tail节点
 5         if (accessOrder && (last = tail) != e) {
 6             //记录当前节点的上一个节点b和下一个节点a
 7             LinkedHashMap.Entry<K,V> p =
 8                     (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
 9             //释放当前节点和后一个节点的关系
10             p.after = null;
11             //如果当前节点的前一个节点为null
12             if (b == null)
13                 //头节点=当前节点的下一个节点
14                 head = a;
15             else
16                 //否则b的后节点指向a
17                 b.after = a;
18             //如果a != null
19             if (a != null)
20                 //a的前一个节点指向b
21                 a.before = b;
22             else
23                 //b设为尾节点
24                 last = b;
25             //如果尾节点为null
26             if (last == null)
27                 //头节点设为p
28                 head = p;
29             else {
30                 //否则将p放到双向链表的最后
31                 p.before = last;
32                 last.after = p;
33             }
34             //将尾节点设为p
35             tail = p;
36             //LinkedHashMap对象操作次数+1,用于快速失败校验
37             ++modCount;
38         }
39     }
复制代码


通过重写put方法,来维护一个双向链表,使得存取有序。。


get()方法

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key); //调用父类的getEntry()方法
    if (e == null)
        return null;
    e.recordAccess(this);  //判断排序方式,如果accessOrder = true , 删除当前e节点
    return e.value;
}
复制代码


  相比于 HashMap 的 get 方法,这里多出了第 5,6行代码,当 accessOrder = true 时,即表示按照最近访问的迭代顺序,会将访问过的元素放在链表后面。


总结


LinkedHashMap比HashMap多了一个双向链表的维护,在数据结构而言它要复杂一些,阅读源码起来比较轻松一些,因为大多都由HashMap实现了..

阅读源码的时候我们会发现多态是无处不在的~子类用父类的方法,子类重写了父类的部分方法即可达到不一样的效果!

比如:LinkedHashMap并没有重写put方法,而put方法内部的newNode()方法重写了。LinkedHashMap调用父类的put方法,里面回调的是重写后的newNode(),从而达到目的!


LinkedHashMap可以设置两种遍历顺序:

  • 访问顺序(access-ordered)
  • 插入顺序(insertion-ordered)
  • 默认是插入顺序的

对于访问顺序,它是LRU(最近最少使用)算法的实现,要使用它要么重写LinkedListMap的几个方法(removeEldestEntry(Map.Entry<K,V> eldest)和afterNodeInsertion(boolean evict)),要么是扩展成LRUMap来使用,不然设置为访问顺序(access-ordered)的用处不大,对于LinkedHashMap的LRU这边没有深入了,因为确实用的不多,但是大家有兴趣的可以深入研究。


LinkedHashMap遍历的是内部维护的双向链表,所以说初始容量对LinkedHashMap遍历是不受影响的

一句话。LinkedHashMap就是继承HashMap的加上双向链表的HashMap,所以讲的也不多


版本说明

  • 这里的源码是JDK8版本,不同版本可能会有所差异,但是基本原理都是一样的。
  • Map家族讲完,整个集合体系,还差一个Set。明天开始Set

因为博主也是一个开发萌新 我也是一边学一边写 我有个目标就是一周 二到三篇 希望能坚持个一年吧 希望各位大佬多提意见,让我多学习,一起进步。


目录
打赏
0
相关文章
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
61 3
Java注解的底层源码剖析与技术认识
Java注解(Annotation)是Java 5引入的一种新特性,它提供了一种在代码中添加元数据(Metadata)的方式。注解本身并不是代码的一部分,它们不会直接影响代码的执行,但可以在编译、类加载和运行时被读取和处理。注解为开发者提供了一种以非侵入性的方式为代码提供额外信息的手段,这些信息可以用于生成文档、编译时检查、运行时处理等。
93 7
[Java计算机毕设]基于ssm的OA办公管理系统的设计与实现,附源码+数据库+论文+开题,包安装调试
OA办公管理系统是一款基于Java和SSM框架开发的B/S架构应用,适用于Windows系统。项目包含管理员、项目管理人员和普通用户三种角色,分别负责系统管理、请假审批、图书借阅等日常办公事务。系统使用Vue、HTML、JavaScript、CSS和LayUI构建前端,后端采用SSM框架,数据库为MySQL,共24张表。提供完整演示视频和详细文档截图,支持远程安装调试,确保顺利运行。
48 17
|
13天前
|
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码
当我们创建一个`ThreadPoolExecutor`的时候,你是否会好奇🤔,它到底发生了什么?比如:我传的拒绝策略、线程工厂是啥时候被使用的? 核心线程数是个啥?最大线程数和它又有什么关系?线程池,它是怎么调度,我们传入的线程?...不要着急,小手手点上关注、点赞、收藏。主播马上从源码的角度带你们探索神秘线程池的世界...
81 0
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码
智慧产科一体化管理平台源码,基于Java,Vue,ElementUI技术开发,二开快捷
智慧产科一体化管理平台覆盖从备孕到产后42天的全流程管理,构建科室协同、医患沟通及智能设备互联平台。通过移动端扫码建卡、自助报道、智能采集数据等手段优化就诊流程,提升孕妇就诊体验,并实现高危孕产妇五色管理和孕妇学校三位一体化管理,全面提升妇幼健康宣教质量。
48 12
Java智慧工地(源码):数字化管理提升施工安全与质量
随着科技的发展,智慧工地已成为建筑行业转型升级的重要手段。依托智能感知设备和云物互联技术,智慧工地为工程管理带来了革命性的变革,实现了项目管理的简单化、远程化和智能化。
39 5
SaaS云计算技术的智慧工地源码,基于Java+Spring Cloud框架开发
智慧工地源码基于微服务+Java+Spring Cloud +UniApp +MySql架构,利用传感器、监控摄像头、AI、大数据等技术,实现施工现场的实时监测、数据分析与智能决策。平台涵盖人员、车辆、视频监控、施工质量、设备、环境和能耗管理七大维度,提供可视化管理、智能化报警、移动智能办公及分布计算存储等功能,全面提升工地的安全性、效率和质量。
8G的容器Java堆才4G怎么就OOM了?
本文记录最近一例Java应用OOM问题的排查过程,希望可以给遇到类似问题的同学提供参考。
基于Java+SpringBoot+Vue实现的车辆充电桩系统设计与实现(系统源码+文档+部署讲解等)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
建筑施工一体化信息管理平台源码,支持微服务架构,采用Java、Spring Cloud、Vue等技术开发。
智慧工地云平台是专为建筑施工领域打造的一体化信息管理平台,利用大数据、云计算、物联网等技术,实现施工区域各系统数据汇总与可视化管理。平台涵盖人员、设备、物料、环境等关键因素的实时监控与数据分析,提供远程指挥、决策支持等功能,提升工作效率,促进产业信息化发展。系统由PC端、APP移动端及项目、监管、数据屏三大平台组成,支持微服务架构,采用Java、Spring Cloud、Vue等技术开发。
115 7
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等