JDK8 HashMap原理分析(上)

简介: JDK8 HashMap原理分析

HashMap的底层存储结构


JDK8中,HashMap是以数组+链表+红黑树的存储结构。


整体上看是一个数组,通过计算元素key的hash值来获取存放位置的数组下标,如果出现hash碰撞,以链表形式存储,称之为,如果链表长度达到8,会转换为红黑树存储,红黑树的引进主要是为了提升查询的性能。


image.png

HashMap的底层存储结构


HashMap常量


//缺省的初始容量16
tatic final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶上的节点数大于阈值时转换为红黑数
static final int TREEIFY_THRESHOLD = 8;
//当桶上节点数小于阈值时转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
//被树化的最小Hash表容量
static final int MIN_TREEIFY_CAPACITY = 64;


HashMap变量


//元素存放表,长度总是2的幂次倍
transient Node<K,V>[] table;
//具体元素存放集合
transient Set<Map.Entry<K,V>> entrySet;
//实际存放键值对数量
transient int size;
//扩容(重hash)或者map结构修改的次数
transient int modCount;
//扩容阈值(容量*负载因子)
int threshold;
//负载因子
final float loadFactor;


Node是对Map中键值对的描述


static class Node<K,V> implements Map.Entry<K,V> {
   //hashCode,不可改变
   final int hash;
   //key不可改变
    final K key;
    V value;
    //指向当前元素的下一个元素,一个桶中形成链表组织
    Node<K,V> next;
    ...
}


HashMap插入元素过程


image.png

put过程.png


解释:


主要流程参考上图基本是清晰的,主要说一下图中标①的地方:


在进行链表添加时,首先判断下一个节点是否为空,为空就说明是链表最后一个节点,直接插入到链表尾部,如果不是最后一个节点,判断key是否存在,如果存在则覆盖value值,如果不存在,则继续链表遍历,直到找到相同key或者遍历完最后一个元素后插入到链表的尾部


对应插入元素源码解释如下

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //桶数组是否为空
        if ((tab = table) == null || (n = tab.length) == 0)
            //为空先进行扩容
            n = (tab = resize()).length;
        //根据hash值计算数组下标,并判断该下标处元素是否为空
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果为空,将元素插入该位置
            tab[i] = newNode(hash, key, value, null);
        else {//如果不为空,说明出现了hash碰撞,插入到桶中
            Node<K,V> e; K k;
            //key是否相同,相同则覆盖元素的value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是TreeNode,则按红黑树插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//如果不是TreeNode,插入到链表中
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //链表元素的下一个节点是否为空,为空插入到链表尾部
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判断链表长度是否超过阈值(8),超过转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //判断key是否存在,key存在则跳出循环,接下来的流程中会覆盖value值,如果key不存在,则继续遍历链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //key存在,覆盖value值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //判断是否需要扩容
        if (++size > threshold)
            resize();
        //为了继承自HashMap的LinkedHashMap而设计
        afterNodeInsertion(evict);
        return null;
    }


相关文章
|
5月前
|
存储 缓存 安全
面试题-HashMap底层原理与HashTable的区别
字节跳动面试题-HashMap底层原理与HashTable的区别
54 0
|
2月前
|
Java
Spring5入门到实战------9、AOP基本概念、底层原理、JDK动态代理实现
这篇文章是Spring5框架的实战教程,深入讲解了AOP的基本概念、如何利用动态代理实现AOP,特别是通过JDK动态代理机制在不修改源代码的情况下为业务逻辑添加新功能,降低代码耦合度,并通过具体代码示例演示了JDK动态代理的实现过程。
Spring5入门到实战------9、AOP基本概念、底层原理、JDK动态代理实现
|
27天前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
|
2月前
|
存储 Java
【Java集合类面试七】、 JDK7和JDK8中的HashMap有什么区别?
JDK7中的HashMap使用数组加链表解决冲突,而JDK8增加了红黑树结构以优化链表过长时的性能,提高查找效率。
|
2月前
|
Java
JDK序列化原理问题之Hessian框架不支持writeObject/readObject方法如何解决
JDK序列化原理问题之Hessian框架不支持writeObject/readObject方法如何解决
|
2月前
|
自然语言处理 JavaScript 前端开发
JDK序列化原理问题之FuryJDK序列化性能问题的如何解决
JDK序列化原理问题之FuryJDK序列化性能问题的如何解决
|
2月前
|
缓存 Java
JDK序列化原理问题之Fury如何实现与JDK序列化100%兼容的如何解决
JDK序列化原理问题之Fury如何实现与JDK序列化100%兼容的如何解决
|
2月前
|
Java
JDK序列化原理问题之在JDK序列化中不同JDK版本字段不一致的情况如何解决
JDK序列化原理问题之在JDK序列化中不同JDK版本字段不一致的情况如何解决
|
4月前
|
Java 编译器
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
43 1
|
3月前
|
监控 算法 Java
怎么用JDK自带工具进行JVM内存分析
JVM内存分析工具,如`jps`、`jcmd`、`jstat`、`jstack`和`jmap`,是诊断和优化Java应用的关键工具。`jps`列出Java进程,`jcmd`执行诊断任务,如查看JVM参数和线程堆栈,`jstat`监控内存和GC,`jstack`生成线程堆栈信息,而`jmap`则用于生成堆转储文件。这些工具帮助排查内存泄漏、优化内存配置、性能调优和异常分析。例如,`jmap -dump:file=heapdump.hprof &lt;PID&gt;`生成堆转储文件,之后可以用Eclipse Memory Analyzer (MAT)等工具分析。