让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: `HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。

分析HashMap的put方法的源码后发现,HashMap的扩容方法在两个场景下会被调用:

  1. 初始化HashMap的链表数组时,会被调用,用来初始化链表数组的初始容量为16,以及初始化链表数组的阈值为初始容量16*负载因子0.75=12;
  2. 当put到HashMap存储的元素个数超过阈值时,会被调用,用来将链表数组的容量和阈值都扩大为原来的2倍。
    具体,详见下述的源码解析:
    /*HashMap的put方法,实际上调用的是putVal方法/
public V put(K key, V value) {
   
        return putVal(hash(key), key, value, false, true);
}
/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key //这里是已经用key的原始hashCode的高16位和低16位异或运算过的hashCode
     * @param key the key //key值 用于计算出要放的数组的索引位置
     * @param value the value to put //value值 数组索引位置上要放置的值
     * @param onlyIfAbsent if true, don't change existing value //false 若为true,则不替换已存在的旧值,但HashMap调用此方法时给的为false,所以会拿要放置的新值替换已存在的旧值
     * @param evict(驱逐) if false, the table is in creation mode. //true 表明数组已构造完毕,可以往里面put了,false则表示数组还在初始化构造中。但此参数在HashMap中并没有实际意义,实际被调用的方法是个空方法:void afterNodeInsertion(boolean evict) { }
     * @return previous value, or null if none//要放的位置上已有旧值则最后返回该旧值,否则返回null
     */
    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)//Node<K,V>[] table,用于装载链表的数组为空,说明数组尚未开始初始化
            n = (tab = resize()).length;//调用扩容方法为数组初始化,初始化完后代码继续往下执行【使用默认容量值和阈值为其初始化,newCap = DEFAULT_INITIAL_CAPACITY (16,must be a power of two);newThr = (int)(DEFAULT_LOAD_FACTOR(0.75) * DEFAULT_INITIAL_CAPACITY)】;
        if ((p = tab[i = (n - 1) & hash]) == null) //判断根据key计算出的要放置的数组的索引位置上是否没值,若没值说明该数组索引位置的链表的头节点还没创建
            tab[i] = newNode(hash, key, value, null);//链表头节点不存在,则调用 Node<>(hash, key, value, next)创建头节点,并初始化头节点的hash,key,value,next=null。 
        else {
   //索引位置已有值,说明链表头节点已存在,则开始具体put操作
            Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//要put的key对应的hash值及key值与链表头节点里的key对应的hash值和key值都相等,则说明该put操作是想要替换头节点,
                e = p;//所以将头节点的引用赋给Node<K,V> e保存下来,以便后续拿来对其继续处理(用要put的新value替换掉旧value,后面可以看到替换值的相关处理)
            else if (p instanceof TreeNode) //若原节点类型为红黑树结构的节点,则调用向树中put的方法TreeNode.putTreeVal
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
   //若非想要替换头节点,且目前该索引位置(桶)的结构类型非红黑树结构,则put到链表的最后一个节点(即next为空的链表的末尾节点)
                for (int binCount = 0; ; ++binCount) {
   binCount用来统计该索引位置上的链表()上元素个数,注意是从0开始第一个计数
                    if ((e = p.next) == null) {
   // 若next(即下一节点)为空,即指链表的末尾节点
                      p.next = newNode(hash, key, value, null);//为要put的键值对创建新节点放在原末尾j节点的next节点,成为新的末尾节点
                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 因binCount是从0开始的,所以当binCount数值为7的时候,统计到的链表元素个数已经达到8个,而当链表长度达到8时,会调用treefyBin方法转成红黑树结构,以便提供更高的增删查改性能
                        treeifyBin(tab, hash); //链表转红黑树,详见《HashMap之链表转红黑树-treefyBin方法》
                      break;//已经找到要操作的节点位置,所以不用再循环,故跳出
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//走到此处说明,要put的键值对既非要替换头节点,也非要在put到红黑树上,也不是要追加到链表末尾节点,而是要替换链表头尾之间的某个节点(因此代码走到此处,就说明要put的key的hash值和key值与链表头尾之间的某个节点的key的hash值和key值都相等)
                        break; //已经找到要操作的节点位置,所以不用再循环,故跳出
                    p = e; //走到这里说明截至目前尚未找到要操作的节点位置,继续下一轮循环(此时的e已经被赋值为了p.next,而此处又将p.next赋给了p,所以下次循环到p.next时,其实是向前递进了一个节点)
                }
            }
            if (e != null) {
    // existing mapping for key  //此处是为了处理上面处理逻辑中余下的替换值的操作,即找到了要处理的节点位置,且在该位置已经有元素存在,需要把该位置上的元素的旧值替换成新值,并返回旧值
                V oldValue = e.value; //记录下旧值,以便return
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; //用新值替换旧值
                afterNodeAccess(e);//Callbacks to allow LinekdHashMap post-actions.供LinkedHashMap后续操作的回调方法(钩子方法),于HashMap而言此方法无意义.
                return oldValue;
            }
        }
        ++modCount; //每次put都会加1(新增而非替换,替换的话在返回旧值处代码就返回了),用于记录变更次数
        if (++size > threshold) //每put一次size都会加1,当size超过此时的容量阈值时,也会发生扩容操作
            resize();//扩容操作
        afterNodeInsertion(evict);//同afterNodeAccess(e),也是供LinkedHashMap后续操作的回调方法,于HashMap而言此方法无实际意义
        return null; //新增操作无旧值可返回
    }
目录
相关文章
|
2月前
|
人工智能
歌词结构的巧妙安排:写歌词的方法与技巧解析,妙笔生词AI智能写歌词软件
歌词创作是一门艺术,关键在于巧妙的结构安排。开头需迅速吸引听众,主体部分要坚实且富有逻辑,结尾则应留下深刻印象。《妙笔生词智能写歌词软件》提供多种 AI 功能,帮助创作者找到灵感,优化歌词结构,写出打动人心的作品。
|
1天前
|
安全 Ubuntu Shell
深入解析 vsftpd 2.3.4 的笑脸漏洞及其检测方法
本文详细解析了 vsftpd 2.3.4 版本中的“笑脸漏洞”,该漏洞允许攻击者通过特定用户名和密码触发后门,获取远程代码执行权限。文章提供了漏洞概述、影响范围及一个 Python 脚本,用于检测目标服务器是否受此漏洞影响。通过连接至目标服务器并尝试登录特定用户名,脚本能够判断服务器是否存在该漏洞,并给出相应的警告信息。
114 84
|
2月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
50 3
|
2月前
|
人工智能
写歌词的技巧和方法全解析:开启你的音乐创作之旅,妙笔生词智能写歌词软件
怀揣音乐梦想,渴望用歌词抒发情感?掌握关键技巧,你也能踏上创作之旅。灵感来自生活点滴,主题明确,语言简洁,韵律和谐。借助“妙笔生词智能写歌词软件”,AI辅助创作,轻松写出动人歌词,实现音乐梦想。
|
12天前
|
负载均衡 网络协议 算法
Docker容器环境中服务发现与负载均衡的技术与方法,涵盖环境变量、DNS、集中式服务发现系统等方式
本文探讨了Docker容器环境中服务发现与负载均衡的技术与方法,涵盖环境变量、DNS、集中式服务发现系统等方式,以及软件负载均衡器、云服务负载均衡、容器编排工具等实现手段,强调两者结合的重要性及面临挑战的应对措施。
33 3
|
29天前
|
JSON PHP 数据格式
PHP解析配置文件的常用方法
INI文件是最常见的配置文件格式之一。
46 12
|
1月前
|
机器学习/深度学习 人工智能 安全
TPAMI:安全强化学习方法、理论与应用综述,慕工大、同济、伯克利等深度解析
【10月更文挑战第27天】强化学习(RL)在实际应用中展现出巨大潜力,但其安全性问题日益凸显。为此,安全强化学习(SRL)应运而生。近日,来自慕尼黑工业大学、同济大学和加州大学伯克利分校的研究人员在《IEEE模式分析与机器智能汇刊》上发表了一篇综述论文,系统介绍了SRL的方法、理论和应用。SRL主要面临安全性定义模糊、探索与利用平衡以及鲁棒性与可靠性等挑战。研究人员提出了基于约束、基于风险和基于监督学习等多种方法来应对这些挑战。
59 2
|
2月前
|
安全 Java
Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧
【10月更文挑战第20天】Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧,包括避免在循环外调用wait()、优先使用notifyAll()、确保线程安全及处理InterruptedException等,帮助读者更好地掌握这些方法的应用。
22 1
|
2月前
|
存储 JavaScript 前端开发
Vue3权限控制全攻略:路由与组件层面的用户角色与权限管理方法深度解析
Vue3权限控制全攻略:路由与组件层面的用户角色与权限管理方法深度解析
180 2
|
2月前
|
SQL 监控 数据库
SQL语句是否都需要解析及其相关技巧和方法
在数据库管理中,SQL(结构化查询语言)语句的使用无处不在,它们负责数据的查询、插入、更新和删除等操作

推荐镜像

更多