让星星⭐月亮告诉你,HashMap在put数据时是如何找到要存放的位置的?

2024-05-14 14:08

本文主要是介绍让星星⭐月亮告诉你,HashMap在put数据时是如何找到要存放的位置的?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

⭐⭐⭐初印象🌙🌙🌙:

初识HashMap时,知道HashMap是用来存放Key-Value这样的键值对的,也知道HashMap的底层数据结构是:数组+链表+红黑树,且数组长度为2的x次幂。

⭐⭐⭐疑问🌙🌙🌙:

那么往HashMap中添加键值对时,是什么决定了键值对的存放位置呢?即存放位置是如何计算出来的呢?相同的疑问可能还会以下面的问题描述方式提出来:
其他描述方式:
1.向HashMap中put数据时,数据是如何找到HashMap中Node<K,V>[] table数组的对应索引下标位置的?
2.HashMap在put<K,V>时是如何找到要存放的数组索引下标的位置的?键值对是如何与数组索引下标产生映射关联关系的?
比如有个HashMap的数组中有16个索引下标位置,一个数据过来要put到HashMap中,是谁来决定该元素会被分配到具体哪个索引下标位置的?如何保证哪块代码处理的?

⭐⭐⭐分析🌙🌙🌙:

既然是由put方法引出的问题,自然要到put的源代码里找寻线索。当我们认真研读put的源码时会发现下面这三段代码,我们分别解读一下:

  1. put调用putVal方法:
    public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    }
  2. 根据Key-键值计算出新的哈希码值:
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
     这段代码里首先调用Object的hashCode()方法,计算出key的原始哈希码;
     然后,将原始哈希码无符号右移了16位,即高16位被移到了低16位(
    问1:为啥做无符号右移操作,即为啥要从高位往低位移动呢?移动后又为何要做异或操作?
    答1:低位不确保有没有1,但高位肯定有1,拿无符号右移后的值与原值做异或操作,可以得到一个1的分布在高低位相对更加均匀的结果。(为啥要得到这样的结果呢?是为了在跟数组长度一起做&与运算计算索引下标时,得到相对更加均匀分撒的结果,这样根据不同key得出的数组索引下标尽可能分撒的话,就不容易发生哈希碰撞,也就降低了一开始往HashMap中添加数据时链表的产生几率)
    问2:为啥又非得是16位呢?
    答2:因为hashCode是一个int整形32位,高16位无符号右移16位,可以保证高位与低位能充分混合,这样的话,再拿无符号右移后的值与原值做异或操作,可以使得1在高低位的分布更加均匀。
    )
     然后无符号右移后的值与原哈希码值做异或操作,得到一个1的分布在高低位相对更加均匀的新哈希码值。
  3. 根据数组长度及新哈希码计算索引位置:
    在put调用的putVal方法的里,有这么一段代码:
    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)
    ………………………………后续代码省略…………………………………………
    注意第2个if语句里隐藏了这么一句:p = tab[i = (n - 1) & hash]
    这里就是根据数组长度和新哈希码值计算数组下标的地方,其中:
     tab从第三段代码可以看到是从table得来的,而table就是HashMap中的存放链表头节点的数组:Node<K,V> table;
     n是数组的长度,为2的x次幂的数,故(n-1)代表的二进制位全是1;
     hash是从第二段代码中得到的新哈希值
     由上可以进而推导出,在公式(n-1)&hash中:
    当hash全为0时,得到最小值为0;
    当hash全为1时,得到最大值为(n-1);
    当hash部分为0部分为1时,得到介于最大值和最小值之间的整数;
    这样就确保了,根据就根据key得到了要存放的数组索引下标,而且该下标肯定会落在数组长度对应的索引范围内。

这篇关于让星星⭐月亮告诉你,HashMap在put数据时是如何找到要存放的位置的?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988948

相关文章

SQL中如何添加数据(常见方法及示例)

《SQL中如何添加数据(常见方法及示例)》SQL全称为StructuredQueryLanguage,是一种用于管理关系数据库的标准编程语言,下面给大家介绍SQL中如何添加数据,感兴趣的朋友一起看看吧... 目录在mysql中,有多种方法可以添加数据。以下是一些常见的方法及其示例。1. 使用INSERT I

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分,使用python生成公钥与私钥,然后保存在两个文

mysql中的数据目录用法及说明

《mysql中的数据目录用法及说明》:本文主要介绍mysql中的数据目录用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、版本3、数据目录4、总结1、背景安装mysql之后,在安装目录下会有一个data目录,我们创建的数据库、创建的表、插入的

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》:本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

SpringBoot中4种数据水平分片策略

《SpringBoot中4种数据水平分片策略》数据水平分片作为一种水平扩展策略,通过将数据分散到多个物理节点上,有效解决了存储容量和性能瓶颈问题,下面小编就来和大家分享4种数据分片策略吧... 目录一、前言二、哈希分片2.1 原理2.2 SpringBoot实现2.3 优缺点分析2.4 适用场景三、范围分片

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat