日志

Java基础之LinkedHashMap原理分析

 来源    2020-09-16    1  

准备知识:HashMap

我们平时用LinkedHashMap的时候,都会写下面这段

LinkedHashMap<String, Object> map = new LinkedHashMap<>();
map.put("student", "333");
map.put("goods", "222");
map.put("product", "222");

然后我们通常都会去看 put 方法,但是我们点到LinkedHashMap内部后,发现没有put方法,这是为什么呢?

其实这个不难,因为LinkedHashMap继承子HashMap

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
}

这就好理解了。因为put是集成自HashMap,那么LinkedHashMap的数据也是 数组+链表 的形式存储的吗?我们慢慢往下看

在HashMap中,put一个数据的时候,会调用一个newNode方法来创建节点,而LinkedHashMap重写了该方法

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMapEntry<K,V> p =
        new LinkedHashMapEntry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

在每次创建节点的时候,都调用了一次linkNodeLast方法,来拼接链表。
tail代表链表尾巴,head代表链表脑袋
entry.before代表前驱
entry.after代表后置

private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    LinkedHashMapEntry<K,V> last = tail;
    tail = p;
    //判断尾部是否是空的,为空就认为链表没创建,拼接在头上
    if (last == null)
        head = p;
    else {
        //在最后一个节点的before上放前一个节点
        p.before = last;
        //在after上放置当前节点
        last.after = p;
    }
}

通过这个方法,我们就对LinkedHashMap有了一个初步的了解了。before和after分别指向前驱和后置,这是典型的双向链表的结构,稍等,我去画个赋予灵魂的配图。

有了这个图就好理解多了~
当我们 put 数据的时候,除了创建节点之外,还有一个操作,就是HashMap会回调一个 afterNodeInsertion方法,我们看一下LinkedHashMap的实现

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMapEntry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

其实这个方法是移出最老的节点,但这段代码在jdk1.8里就不在被执行了,除非你自己集成LinkedHashMap重写removeEldestEntry方法。因为removeEldestEntry=false,OK,当我们在put数据的时候,整个双链表就建立起来了,接下来我们看下get有什么操作吧

final boolean accessOrder;
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //顺序访问模式
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

LinkedHashMap的get操作首先会从 HashMap 维护的数据中通过hash获取Node,然后判断accessOrder属性,如果等于true就调用afterNodeAccess方法

那么accessOrder是个什么呢?有什么用呢?
其实accessOrder是个标记位,用来标记数据是否按照访问顺序处理,如果设置为true,那么我们每次访问数据,这个数据都会被移动到链表尾部,就会导致链表尾部的访问频次是最高的(年老的变量),链表头部是访问频次最低的(年轻的变量),这个特性正好适合做LRU缓存。如果设置为false,也就是默认的模式,那么就是按照存储顺序存储数据,访问也不会触发置尾操作。我们接下来看一下它是怎么做到的置尾吧。

首先通过这个构造方法,把accessOrder初始化成true,默认是false

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

然后我们试一下效果

Map<String, String> map = new LinkedHashMap<>(
        1 << 4, 0.75f, true
);
map.put("node1", "node1");
map.put("node2", "node1");
map.put("node3", "node1");
map.put("node4", "node1");
map.get("node1");
System.out.println(map);

{node2=node1, node3=node1, node4=node1, node1=node1}

和预期一样,访问了一次node1,它就把node1放在链表的尾巴上了,这个操作主要是在afterNodeAccess内,我们接下来看下是怎么实现的吧

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.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;
        //如果我们get的数据是表头的数据,那么表头就需要更新为表头的后置
        //比如node1->node2->node3,我们获取node1的时候,node1要跑到队尾
        //所以node2就是老大
        if (b == null)
            head = a;
        else
            //否则的话,把get的数据的前置节点和get的数据的后置节点连接
            //比如,get node2,node2的before正是node1
            //因为node2要去队尾了,所以node1就不能在绑定after为node2了,要改成node3
            b.after = a;
        //a等于空说明p是队尾。因为只有队尾的后置节点是空的
        if (a != null)
            //把操作数据的后置节点连接上操作数据的前置节点
            //比如,get node2,node的after便是node3
            //node3的before在没改变的时候是node2,结果node2要去队尾,所以要连接都node1去
            a.before = b;
        else
            //a等于空说明什么?说明p的后置节点是空的。说明p可能是队尾
            last = b;
        //假设last等于b的时候。结果b是空的,按照规则,before为空就要成为头
        if (last == null)
            head = p;
        else {
            //把操作数据的前置节点设置成队尾,准备去队尾了。。。
            p.before = last;
            //把刚才队尾的后置节点,设置成刚刚操作的node2,实锤了,真的都队尾了
            last.after = p;
        }
        //执行队尾赋值
        tail = p;
        ++modCount;
    }
}

这个方法我在啰嗦总结一下吧
1.先把操作数据的前置和后置找处理
2.然后把它前置和它后置做链接
3.把它的前置链接到之前的队尾上,再把之前的队尾的后置链接到它身上
4.最后把队尾改成操作的数据即可
最后再让我这个灵魂画手配张图吧~

最后聊一下resize吧。既然是集成自HashMap,那么肯定也是到达了扩容阀值就要扩容的

我们去找LinkedhashMap内部,发现没有重写resize,那就说明它的扩容是由父类HashMap完成的。具体的扩容过程,可以看我另一篇讲解HashMap的文章

相关文章
Java基础(三)-final关键字分析
日志一 引言 今天来谈谈final关键字的作用, 虽然有很多博文关于final进行了很深的研究,但还是要去记录下谈谈自己的见解加深下印象.下面直接进入主题: 二 final关键字的作用 1.被final修 ...
1
Java基础(二)-static关键字分析
日志一.前言 static关键字是我们在编程中经常会使用到的,但有些可能只知其然而不知其所以然.下面介绍static关键字的作用再通过例子结合说明. static关键字共有五种作用(先说明static所修 ...
1
Java原子类实现原理分析
日志并发包中的原子类可以解决类似num++这样的复合类操作的原子性问题,相比锁机制,使用原子类更精巧轻量,性能开销更小,下面就一起来分析下原子类的实现机理. 悲观的解决方案(阻塞同步) 我们知道,num+ ...
1
JAVA基础之——Thrift原理及应用
日志1 是什么 是为了解决facebook系统中各系统间大数据量的传输通信,以及系统之间语言环境不同需要跨平台的问题. 是一种实现RPC的软件框架,自定义IDL(Interface description ...
1
支付宝app支付java后台流程、原理分析(含nei wang chuan tou)
日志 java版支付宝app支付流程及原理分析 本实例是基于springmvc框架编写     一.流程步骤         1.执行流程           当手机端app(就是你公司开发的app)在支 ...
1
Java 8 Lambda实现原理分析
日志PDF文档已上传Github  Github:https://github.com/zwjlpeng/Angrily_Learn_Java_8 为了支持函数式编程,Java 8引入了Lambda表达式 ...
1
Java集合:ConcurrentHashMap原理分析
日志 集合是编程中最常用的数据结构.而谈到并发,几乎总是离不开集合这类高级数据结构的支持.比如两个线程需要同时访问一个中间临界区(Queue),比如常会用缓存作为外部文件的副本(HashMap).这篇文章 ...
Java中的递归原理分析
日志解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法 ...
java基础---->hashSet的简单分析(一)
日志对于HashSet而言,它是基于HashMap实现的,底层采用HashMap来保存元素的.今天我们就简单的分析一下它的实现.人生,总会有不期而遇的温暖,和生生不息的希望.  HashSet的简单分析 ...
java基础---->hashMap的简单分析(一)
日志HashMap是一种十分常用的数据结构对象,可以保存键值对.它在项目中用的比较多,今天我们就来学习一下关于它的知识.据说那些你一笑就跟着你笑的人,不是傻逼就是爱你的人. HashMap的简单使用 一. ...
1
java集合框架使用原理分析
日志      集合是我们日常编程中可能用的很多的技术之一 使用频率极高 可能平时就会知道怎么去用 但是集合之间的关系与不同之处都不是很清楚 对它们的底层原理更甚 所以写词文章 让自己有一个更深的认识 集 ...
1
Java面试& HashMap实现原理分析
日志1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端.  数组 数组存储区间是连续的,占用内存严重,故空间复杂的很大.但数组的二分查找时间复杂度小,为O( ...
1
微信app支付java后台流程、原理分析及nei网穿透
日志一.流程步骤 本实例是基于springmvc框架编写 1.执行流程           当手机端app(就是你公司开发的app)在支付页面时,调起服务端(后台第1个创建订单接口)接口,后台把需要调起微 ...
1
Java基础之多线程详细分析
日志 在了解多线程之前,先来了解一下进程与线程之间的关系. 进程和线程: 进程是指在系统中正在执行的一个程序,每个进程之间是独立的. 线程是进程的一个基本执行单元.一个进程要想执行任务,必须得有线程(每1 ...
Java类载入器原理分析
日志一:Java虚拟机中能够安装多个类载入器,系统默认是三个基本的类载入器: Bootstrap  ExtClassLoader  AppClassLoader 类载入器也是Java类.由于其它Java类 ...
夯实Java基础系列3:一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!
日志目录 string基础 Java String 类 创建字符串 StringDemo.java 文件代码: String基本用法 创建String对象的常用方法 String中常用的方法,用法如图所示 ...
2
java基础解析系列(四)---LinkedHashMap的原理及LRU算法的实现
日志java基础解析系列(四)---LinkedHashMap的原理及LRU算法的实现 java基础解析系列(一)---String.StringBuffer.StringBuilder java基础解析 ...
3
java基础解析系列(七)---ThreadLocal原理分析
日志java基础解析系列(七)---ThreadLocal原理分析 目录 java基础解析系列(一)---String.StringBuffer.StringBuilder java基础解析系列(二)-- ...
1
JAVA基础加强(张孝祥)_类加载器、分析代理类的作用与原理及AOP概念、分析JVM动态生成的类、实现类似Spring的可配置的AOP框架
日志1.类加载器 ·简要介绍什么是类加载器,和类加载器的作用 ·Java虚拟机中可以安装多个类加载器,系统默认三个主要类加载器,每个类负责加载特定位置的类:BootStrap,ExtClassLoader ...
夯实Java基础系列4:一文了解final关键字的特性、使用方法,以及实现原理
日志目录 final使用 final变量 final修饰基本数据类型变量和引用 final类 final关键字的知识点 final关键字的最佳实践 final的用法 关于空白final final内存分配 ...
1