让星星⭐月亮告诉你,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

相关文章

C#监听txt文档获取新数据方式

《C#监听txt文档获取新数据方式》文章介绍通过监听txt文件获取最新数据,并实现开机自启动、禁用窗口关闭按钮、阻止Ctrl+C中断及防止程序退出等功能,代码整合于主函数中,供参考学习... 目录前言一、监听txt文档增加数据二、其他功能1. 设置开机自启动2. 禁止控制台窗口关闭按钮3. 阻止Ctrl +

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

C#解析JSON数据全攻略指南

《C#解析JSON数据全攻略指南》这篇文章主要为大家详细介绍了使用C#解析JSON数据全攻略指南,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、为什么jsON是C#开发必修课?二、四步搞定网络JSON数据1. 获取数据 - HttpClient最佳实践2. 动态解析 - 快速

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

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生成公钥与私钥,然后保存在两个文