百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术分类 > 正文

Java源码解析篇:HashMap(java hashmap工作原理)

ztj100 2025-03-20 21:15 15 浏览 0 评论

相信大家对HashMap的底层原理或多或少都有了解,这里简单提一下,jdk1.8版本之后HashMap内部主要通过数组+链表+红黑树的数据结构来存放元素,本文我们来分析HashMap的几个主要方法,看看HashMap的源码具体是如何实现的,以及jdk做了哪些优化来提升性能。

Node节点

Bash
static class Node implements Map.Entry {
    //hash值
    final int hash;
    //元素的key
    final K key;
    //元素的值
    V value;
    //指向下一个节点
    Node next;

    //此处省略其他代码。。。
}
复制代码

Node类是以HashMap的内部类形式存在,代表放入HashMap的元素,字段含义都比较好理解,这里的next字段表示一个指针,指向下一个节点,等会在put方法里分析这个字段的使用场景

put方法

Bash
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
复制代码

put方法直接调用了putVal方法,可以看到第一个参数传入了hash(key),那我们先来看一下hash方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

这个hash方法就是用来计算放入map方法的元素的hash值,重点是这段代码(h = key.hashCode()) ^ (h >>> 16),先通过key.hashCode()获取key的hash值,然后再异或(h >>> 16)计算出最终的hash值,h>>>16表示将hash值右移16位

如果对右移>>>和异或^运算不熟悉的同学,看这行代码可能会比较疑惑,举个栗子:

h值:
1111 1111 1111 1111 1111 1010 0111 1100

h>>>16值:
0000 0000 0000 0000 1111 1111 1111 1111

h ^ (h >>> 16)值:
1111 1111 1111 1111 0000 0101 1000 0011

最终通过h ^ (h >>> 16)计算出来的值才是hash方法获取到的hash值,那么这里为什么要先右移再异或来获取hash值,而不是直接返回hashCode方法拿到的hash值呢?一句话解释就是:为了降低hash冲突,至于为什么能降低hash冲突,我们在后面讲定位元素在数组上的位置的时候再来解释,这里只要知道通过异或操作能将原始hash的高低16位的特征都保留下来,反应在最终的hash值上

hash方法分析完了之后,我们来看下putVal方法,这个方法比较长,里面分支逻辑也比较复杂,我们一点一点来看

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //1.数组为空,先调用resize方法生成一个数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //2.先定位元素在数组中的位置,如果当前位置元素为空,构建一个Node放入当前位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //3.当前位置已经存在元素且key相同,直接覆盖当前元素
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //4.如果当前元素是一个树节点,将新元素挂到树上
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            //5.将元素挂到链表上
            else {
                //6.遍历链表元素
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //7.构建一个节点,这里就是用next指针来链接节点
                        p.next = newNode(hash, key, value, null);
                        //8.如果链表上的元素超过8个,转成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //9.如果当前元素和新元素key相同,直接覆盖链表上的节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            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();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

上面的代码中,我在各个重要代码上加了注释,应该很容易理解,我们来看下几个比较重要的点:

1.定位元素位置:p = tab[i = (n - 1) & hash]

还记得前面留下的问题吗,为什么hash方法要移位和异或操作,这里就来解释清楚,在获取到hash值之后,(n - 1) & hash将hash和数组长度减1进行与操作定位元素在数组上的位置,n在代码里保证了是2的幂次方,比如16、32、64等等,看完这个方法也就明白了为什么要是2的幂次方,同样,我们来举个栗子看看这个操作:

n值假设是16,那么n-1就是15,二进制值为:1111

hash值就用上面的1111 1111 1111 1111 0000 0101 1000 0011,两者取与,结果是11,所以这个元素就会落在索引为11的位置上,这里用与操作而不是对数组取模,主要还是因为性能上的考虑。

那么为什么要用异或操作呢,我们假定前面那个元素叫a,原始hash值是1111 1111 1111 1111 1111 1010 0111 1100,还有另一个元素b的原始hash值是1111 1111 1111 1110 1111 1010 0111 1100,注意和之前元素的区别,它们只有第16位不一样,a是1,b是0

如果没有进行移位和异或操作,那么它俩进行(n - 1) & hash计算之后值是一样的,都是16,也就是会产生冲突,我们再来看看b经过移位和异或操作之后的hash值是什么

b的h值:
1111 1111 1111 1110 1111 1010 0111 1100

h>>>16值:
0000 0000 0000 0000 1111 1111 1111 1110

h ^ (h >>> 16)值:
1111 1111 1111 1111 0000 0101 1000 0010

所以b最终的hash值为1111 1111 1111 1111 0000 0101 1000 0010,求与(n - 1) & hash之后就是10,也就是定位到了索引为10的数组位置,和a不冲突了,感受到了么,这就是移位和异或的作用,降低元素在数组位置上冲突的概率。

2.链表转红黑树: treeifyBin(tab, hash); 这个方法简单来说就是将链表转成了一颗红黑树,内部实现还是很复杂的,有兴趣的可以自己去看源码。

resize方法

Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
    next = e.next;
    //1.hash值&老数组长度等于0
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    //2.hash值&老数组长度不等于0
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    //3.放到新数组的原位置
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    //4.放到(老数组长度+原位置)的新位置
    newTab[j + oldCap] = hiHead;
}
复制代码

HashMap扩容的时候会先生成一个容量为老数组2倍的新数组,然后将老元素拷贝到新数组上,上面代码是从resize方法里摘出来的确定扩容之后新元素位置的代码,注释1那里通过元素hash值和原数组长度取余是否为0就可以快速确定放在新数组的位置,如果为0,就放在老位置,如果不为0就放在新位置,新位置通过老数组长度+原位置来确定,同样,我们来举个栗子理解一下:

假设,hash为1111 1111 1111 1111 0000 0101 1000 0011,数组从16扩容到32,通过e.hash & oldCap计算值为0,所以在新旧数组上的位置都是11

另有hash为1111 1111 1111 1111 0000 0101 1001 0011的元素,数组从16扩容到32,通过e.hash & oldCap计算值为1,所以在新数组上的位置就变成了11 + 16 = 27,不再是原来是的11

总结

本文主要讲述了HashMap以下几个实现:
1.计算hash值(移位、异或操作)
2.寻址算法优化(&操作代替取模)
3.put()方法实现(挂链表以及链表转红黑树)
4.resize方法实现(rehash定位新数组中的位置)

以上,希望对你理解HashMap有帮助,有不同看法或疑问欢迎随时和我讨论


作者:haixiang
链接:
https://juejin.cn/post/6986447578111934500

来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关推荐

Java网络编程(JAVA网络编程技术)

网络编程三要素1.IP地址:表示设备在网络中的地址,是网络中设备的唯一标识2.端口号:应用程序在设备中唯一的标识3.协议:连接和数据在网络中传输的规则。InetAddress类Java中也有一个...

字节Java全能手册火了!多线程/网络/性能调优/框架啥都有

前言在这个技术不断更新的年代,跟不上时代变化的速度就会被刷掉,特别是咱们程序员这一群体,技术不断更新的同时也要同时进步,不然长江后浪推前浪,前浪......一个程序员从一个什么都不懂的小白在学到有一定...

一分钟了解java网络编程(java基础网络编程)

一、OSI七层网络模型应用层:Http协议、电子邮件传输、文件服务器等;表示层:数据转换,解决不同系统的兼容问题(跨语言);会话层:建立与应用程序的会话连接;传输层:提供了端口号和传输协议(TPC/U...

Java编程-高并发情况下接口性能优化实践-提升吞吐量TPS

记得前段时间工作中接到一个任务是优化一个下单接口的性能提高接口的吞吐量TPS,前期通过arthas工具跟踪接口的具体方法调用链路及耗时,发现了影响此接口的性能瓶颈主要是加锁的方式,后来变更了锁的方式...

socket 断线重连和心跳机制如何实现?

一、socket概念1.套接字(socket)是网络通信的基石,是支持TCP/IP协议的网络通信的基本操作单元。它是网络通信过程中端点的抽象表示,包含进行网络通信必须的五种信息:连接使用的协议,...

迅速了解-Java网络编程(java基础网络编程)

Java网络编程在JavaSE阶段,我们学习了I/O流,既然I/O流如此强大,那么能否跨越不同的主机进行I/O操作呢?这就要提到Java的网络编程了。...

Java网络编程详解(java 网络编程)

网络编程基础知识最!最!最!重要网络编程基础概念网络编程不等于网站编程,网络编程即使用套接字(socket)来达到各进程间的通信,现在一般称为TCP/IP编程;网络编程分为服务端和客户端。服务端就相当...

「开源推荐」高性能网络通信框架 HP-Socket v5.7.2

简介HP-Socket是一套通用的高性能TCP/UDP/HTTP通信框架,包含服务端组件、客户端组件和Agent组件,广泛适用于各种不同应用场景的TCP/UDP/HTTP通信系统,提供C/...

Java网络编程从入门到精通:打造属于你的网络世界

Java网络编程从入门到精通:打造属于你的网络世界在当今这个信息爆炸的时代,网络编程已经成为程序员必不可少的一项技能。而Java作为一种功能强大且广泛使用的编程语言,在网络编程领域也有着举足轻重的地位...

5分钟读懂C#中TcpClient、TcpListener和Socket三个类的角色

一、核心功能与定位1.Socket类:底层通信的基石-位于System.Net.Sockets命名空间,提供对网络协议栈的直接操作,支持TCP、UDP等多种协议。-手动管理连接细节:需...

(三)谈谈 IO 模型(Socket 编程篇)

快过年啦,估计很多朋友已在摸鱼的路上。而我为了兄弟们年后的追逐,却在苦苦寻觅、规划,导致文章更新晚了些,各位猿粉谅解。上期分享,我们结合新春送祝福的场景,通过一坨坨的代码让BIO、NIO编程过程呈...

大数据编程入门:Java网络编程(大数据 编程)

如果想要编写出一个可以运行在多个设备上的程序,应该怎么做呢?答案是网络编程,今天小编将为大家带来大数据编程入门:Java网络编程。一、网络编程概念网络编程是指编写在通过网络连接的多个设备(计算机)上运...

基于JAVA的社交聊天室(java聊天设计与实现)

基于Java的社交聊天室一、前言随着互联网技术的迅速发展,实时通信和在线社交已成为人们日常生活的重要组成部分。基于Java的社交聊天室系统,凭借其跨平台、高性能和安全性等特点,为用户提供了一个集中、开...

java-socket长连接demo体验(java socket长连接)

作者:DavidDing来源:https://zhuanlan.zhihu.com/p/56135195一、前言最近公司在预研设备app端与服务端的交互方案,主要方案有:服务端和app端通过阿里i...

JAVA数据库编程(java数据库编程指南)

预计更新###第一节:什么是JAVA-JAVA的背景和历史-JAVA的特点和应用领域-如何安装和配置JAVA开发环境###第二节:JAVA基础语法-JAVA的基本数据类型和变量-运算符和...

取消回复欢迎 发表评论: