首页 > 编程语言 >HashMap 源码分析

HashMap 源码分析

时间:2024-04-06 18:30:39浏览次数:22  
标签:分析 hash HashMap tab 链表 源码 key put null

一、序言

本文探讨 HashMap put() 方法的源码。

二、put() 方法核心逻辑流程概览

在这里插入图片描述

当使用 put() 方法插入数据时:

  1. 首先,计算该数据应该放入的索引位置
  2. 如果计算出的索引位置没有发生 hash 冲突,那么数据可以直接插入
  3. 若发生了 hash 冲突,那么就执行红黑树或链表的 put 逻辑
  4. 红黑树 put 逻辑比较特殊,将会在后面的文章中详解(敬请期待)
  5. 执行链表逻辑时,首先会判断链表:是否已存在要插入数据的 key
  6. 若已存在 key,直接更新 value(这也是 HashMap 数据不重复的原因)
  7. 若不存在 key,新建一个包含该数据的节点插入链表尾部(尾插法)
  8. 链表插入成功。之后,判断链表是否满足转换成红黑树的条件
  9. 若条件满足,则将链表转换成红黑树
  10. 若条件不满足,不做任何处理
  11. put 逻辑在结束之后,会检查 HashMap 是否需要扩容
  12. 若需要,则执行扩容逻辑(保证了下次有多余空间进行 put 操作)
  13. 若不需要,则不做任何处理
  14. 至此,put 的流程结束

三、未发生 hash 冲突逻辑流程

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

在 HashMap 中,下标索引是通过 hash 值得到的,而 hash 值是通过上面的 hash 方法获取。该 hash 方法获取 hash 值的逻辑是:key 的 hashCode 值抑或上 key 的 hashCode 无符号右移 16 位的值。

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;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 省去 hash 冲突的代码
    }

    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上述代码是 HashMap 的 put() 方法的底层源码,仅省略了 hash 冲突的代码。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {

    /*
    	1. Node<K,V>[] tab 表示 HashMap 的数据存储结构
		2. Node<K,V> p 表示当前插入的节点,即要存储的键值对。
        3. int n 表示数组的长度,即 table 的大小。
        4. int i 表示计算出的存储位置的索引,通过 (n - 1) & hash 计算得到。
	*/
    Node<K,V>[] tab; Node<K,V> p; int n, i;

	// 判断 HashMap 表是否初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 没有初始化,执行 resize() 扩容
        n = (tab = resize()).length;
    // 判断是否发生 hash 冲突
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 并未发生 hash 冲突,直接插入
        tab[i] = newNode(hash, key, value, null);
    // 表示发生了 hash 冲突
    else {
        // 省去 hash 冲突的代码
    }

    // modeCount + 1 (modCount 是一个成员变量)
    ++modCount;
    // 判断是否需要执行扩容
    if (++size > threshold)
        // 需要扩容,执行 resize() 方法扩容
        resize();
    // 在 HashMap 中这是一个空方法(空方法没有内容,可当作没有这行代码)
    // 若想了解 afterNodeInsertion() 方法的作用可借助搜索引擎
    afterNodeInsertion(evict);

    // 返回 null
    return null;
}

上述源码的逻辑流程如下:

在这里插入图片描述

四、发生 hash 冲突逻辑流程

Node<K,V> e; K k;

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        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;
}

上述代码,是发生 hash 冲突之后的处理逻辑,也就是在之前 else 中省略的代码。上面的代码用来讨论不够清晰,我们将使用下面的逻辑流程图来讨论。

在这里插入图片描述

  1. 发生 hash 冲突之后,首先会判断 key 是否存在(即还未进入链表或红黑树之前,检查数组位置是否已存在此 key)
  2. 若存在,更新 value结束 hash 冲突处理流程
  3. 若不存在,判断是否为 TreeNode(即表示是否为红黑树)
  4. 若是红黑树,则执行红黑树的 put 逻辑(此处暂时省略,敬请期待后续)
  5. 若不是红黑树,则是链表,循环遍历链表
  6. 遍历过程中,判断当前遍历的节点是不是最后一个节点
  7. 若不是,则检查当前遍历节点的 key 是不是与需要 put 的 key 相同
  8. 若 key 相同,更新 value,跳出循环,结束 hash 冲突处理流程
  9. 若 key 不同,开启下一次循环
  10. 若已到达最后一个节点,直接在最后一个节点后插入(尾插法),接下来判断链表长度是否大于阈值 8
  11. 若小于阈值,直接结束 hash 冲突处理流程
  12. 若大于阈值,链表转化成红黑树结束 hash 冲突处理流程
  13. 至此,hash 冲突处理流程结束

五、put() 方法整体逻辑流程

在这里插入图片描述

标签:分析,hash,HashMap,tab,链表,源码,key,put,null
From: https://blog.csdn.net/LearnerDL/article/details/137411638

相关文章

  • 【包远程安装运行】:SpringBoot+Mysql健身房在线预约管理系统源码+运行视频+开发文档(参
    今天发布的是由【猿来入此】的优秀学员独立做的一个基于springboot脚手架的健身房在线预约管理系统,系统分四个角色,管理员,职工、教练、前台用户,各角色功能如下:管理员:系统管理(角色、权限、菜单等)、职工管理、健身会员管理、会员充值管理、健身项目管理、健身百科管理、健身......
  • 【MATLAB源码-第170期】基于matlab的BP神经网络股票价格预测GUI界面附带详细文档说明
    操作环境:MATLAB2022a1、算法描述基于BP神经网络的股票价格预测是一种利用人工神经网络中的反向传播(Backpropagation,简称BP)算法来预测股票市场价格变化的技术。这种方法通过模拟人脑的处理方式,尝试捕捉股票市场中的复杂非线性关系,以实现对未来股价的预测。本文将详细介绍BP......
  • 【MATLAB源码-第171期】基于matlab的布谷鸟优化算法(COA)无人机三维路径规划,输出做短路
    操作环境:MATLAB2022a1、算法描述布谷鸟优化算法(CuckooOptimizationAlgorithm,COA)是一种启发式搜索算法,其设计灵感源自于布谷鸟的独特生活习性,尤其是它们的寄生繁殖行为。该算法通过模拟布谷鸟在自然界中的行为特点,为解决各种复杂的优化问题提供了一种新颖的方法。从算法......
  • 基于java中的springboot实现海滨体育馆管理系统的设计与实现演示【附项目源码+论文说
    基于springboot实海滨体育馆管理系统的设计与实现演示摘要本基于SpringBoot的海滨体育馆管理系统设计目标是实现海滨体育馆的信息化管理,提高管理效率,使得海滨体育馆管理工作规范化、高效化。本文重点阐述了海滨体育馆管理系统的开发过程,以实际运用为开发背景,基于Spring......
  • 基于java中的springboot框架实现服装销售平台系统【附项目源码+论文说明】
    基于SpringBoot实现服装销售平台系统设计演示摘要随着信息互联网购物的飞速发展,一般企业都去创建属于自己的电商平台以及购物管理系统。本文介绍了“衣依”服装销售平台的开发全过程。通过分析企业对于“衣依”服装销售平台的需求,创建了一个计算机管理“衣依”服装销售平......
  • Vue | 底层分析
    一、下载vueGit仓库地址:https://github.com/vuejs/vue.gitGitclonehttps://github.com/vuejs/vue.gitPnpminstall(vue是用pnpm管理工具,用npm会报错,用yarn会找不到依赖包)Pnpmrundev学习思路:先自己搜索->描述->再深入源码学习 二、变化侦测0、现象在da......
  • django图书推荐系统 计算机专业毕业设计源码89399
    摘 要随着时代的不断更新,社会的不断变换,信息技术的飞速发展,计算机科技技术也逐步走向成熟。图书推荐系统对于当今社会来说是必不可少的一个信息组成部分,它可以管理大量图书、大量读者、让读者有条不紊的进行评分图书,大大减小了工作量,并且提高了工作效率。本文研究的图书推......
  • 浅谈威廉希尔足球app比分源码Java算法
    我写了一套足球篮球比分的助手,说起来和澳客的口袋app有点相似,我仿照了它需要研究源码的朋友可以交流下目前项目已经线下实体店投入运营前端支持Android和iOS后台是Java威廉希尔足球app78888.ME ......
  • Java斐波那契查找知识点(含面试大厂题和源码)
    斐波那契查找(FibonacciSearch)是一种在有序数组中查找元素的高效算法,它基于斐波那契数列的性质。斐波那契查找是二分查找的一种改进,通过使用斐波那契数列来确定搜索范围,可以在某些情况下减少比较次数,特别是在数组较大时表现更为出色。以下是斐波那契查找的一些关键知识点:......
  • 【附源码】JAVA计算机毕业设计足球青训俱乐部管理后台系统(springboot+mysql+开题+论文
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着足球运动的日益普及,足球青训作为培养足球后备人才的重要基地,其管理和发展逐渐受到广泛关注。然而,传统的青训俱乐部管理方式往往存在着信息化程度......