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

简介: HashMap 是一种常用的键值对存储结构,其底层采用数组+链表+红黑树实现。本文探讨了 HashMap 在插入键值对时如何确定存放位置。通过分析 `put` 方法的源代码,重点解析了哈希码的计算过程和数组索引的确定方法。哈希码通过 `hashCode()` 方法和位运算优化,确保均匀分布,从而减少哈希碰撞,提高性能。最终,通过 `(n-1) & hash` 计算出数组索引,确保键值对被正确存放到指定位置。

⭐⭐⭐初印象🌙🌙🌙:

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

⭐⭐⭐疑问🌙🌙🌙:

那么往HashMap中添加键值对时,是什么决定了键值对的存放位置呢?即存放位置是如何计算出来的呢?相同的疑问可能还会以下面的问题描述方式提出来:
其他描述方式:
1.向HashMap中put数据时,数据是如何找到HashMap中Node[] table数组的对应索引下标位置的?
2.HashMap在put时是如何找到要存放的数组索引下标的位置的?键值对是如何与数组索引下标产生映射关联关系的?
比如有个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[] tab; Node 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 table;
     n是数组的长度,为2的x次幂的数,故(n-1)代表的二进制位全是1;
     hash是从第二段代码中得到的新哈希值
     由上可以进而推导出,在公式(n-1)&hash中:
    当hash全为0时,得到最小值为0;
    当hash全为1时,得到最大值为(n-1);
    当hash部分为0部分为1时,得到介于最大值和最小值之间的整数;
    这样就确保了,根据就根据key得到了要存放的数组索引下标,而且该下标肯定会落在数组长度对应的索引范围内。
目录
相关文章
|
12月前
|
Java
让星星⭐月亮告诉你,HashMap中保证红黑树根节点一定是对应链表头节点moveRootToFront()方法源码解读
当红黑树的根节点不是其对应链表的头节点时,通过调整指针的方式将其移动至链表头部。具体步骤包括:从链表中移除根节点,更新根节点及其前后节点的指针,确保根节点成为新的头节点,并保持链表结构的完整性。此过程在Java的`HashMap$TreeNode.moveRootToFront()`方法中实现,确保了高效的数据访问与管理。
87 2
|
12月前
|
Java 索引
让星星⭐月亮告诉你,HashMap之往红黑树添加元素-putTreeVal方法源码解读
本文详细解析了Java `HashMap` 中 `putTreeVal` 方法的源码,该方法用于在红黑树中添加元素。当数组索引位置已存在红黑树类型的元素时,会调用此方法。具体步骤包括:从根节点开始遍历红黑树,找到合适位置插入新元素,调整节点指针,保持红黑树平衡,并确保根节点是链表头节点。通过源码解析,帮助读者深入理解 `HashMap` 的内部实现机制。
139 2
|
7月前
|
索引
HashMap的put方法的具体流程?
1. 判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; 2. 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向 ⑥,如果table[i]不为空,转向③; 3. 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的 是hashCode以及equals; 4. 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值 对,否则转向5; 5. 遍历table[i],判断链表长度是否大于8,大于8的
|
10月前
|
存储 缓存 Java
HashMap源码剖析-put流程
更好地掌握 `HashMap` 的内部实现原理,提高编写高效代码的能力。掌握这些原理不仅有助于优化性能,还可以帮助解决实际开发中的问题。
211 13
|
12月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
167 5
|
12月前
|
算法 索引
让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)
`HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。
202 3
|
12月前
|
Java 索引
让星星⭐月亮告诉你,HashMap中红黑树TreeNode的split方法源码解读
本文详细解析了Java中`HashMap`的`TreeNode`类的`split`方法,该方法主要用于在`HashMap`扩容时将红黑树节点从旧数组迁移到新数组,并根据`(e.hash & oldCap)`的结果将节点分为低位和高位两个子树。低位子树如果元素数少于等于6,则进行去树化操作;若多于6且高位子树非空,则进行树化操作,确保数据结构的高效性。文中还介绍了`untreeify`和`replacementNode`方法,分别用于将红黑树节点转换为普通链表节点。
160 2
|
12月前
|
机器学习/深度学习 算法
让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)
`HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括: 1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。 2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。 3. 最终加 1,确保返回值为 2 的幂次方。 该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。
116 1
|
12月前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
210 0
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
196 3