HashMap 扩容原理

矫情吗；* 2023-01-12 01:56 174阅读 0赞

**今天有个朋友问我， 为啥hashMap扩容之后 数组的位置是 当前位置 或 当前位置 + oldCap 呢？**

**想了一下，举个例子最清楚了**

我们模拟一下就清楚了，分别用两个key 进行确认数组位置 .我们默认全部每次扩容都是计算hash出来的结果  
默认两个key  
key1.hash = 40 转换成二进制 101000  
key2.hash = 19 转换成二进制 010011

默认数组长度 16 ==> 转换二进制 10000 ， 由于是 newTab\[e.hash & (newCap - 1)\] = e; 所以最终 15 = 01111

默认分配  
key1.hash = 40 与 19

101000 40  
001111 15  
\-------  
001000 在数组第8位

key2.hash = 19 转换成二进制 010011

010011 19  
001111 15  
\------  
000011 在第3位

=================================================扩容之后===========================  
  
默认数组长度 16<<1 = 32 ==> 转换二进制 100000 ， 由于是 newTab\[e.hash & (newCap - 1)\] = e; 所以最终 31 = 011111

key1.hash = 40 与 19  
0101000 40  
0011111 31  
\-------  
0001000 在数组第8位

key2.hash = 19 转换成二进制 100011

0010011 19  
0011111 31  
\-------  
0010011 在第19位 等于 原长度oldLen16 + 之前所有位置3

如果每次都这样就算，太浪费时间了  
所以找寻规律

发现是否需要 加上原长度 只要将自己的hash 和oldLen(16)进行一次&就可以了

key1.hash = 40 转换成二进制 101000 位置在 8  
key2.hash = 19 转换成二进制 010011 位置在3

扩容判断 -- 每次都全量计算hash 性能很差， 可以做一次优化  
key1.hash= 40

0101000 40  
0010000 16  
\--------  
0000000 0 = 0 ?还是在原先位置

key2.hash = 19  
0010011 19  
0010000 16  
\--------  
0010000 16 !=0 那就是需要 newTab\[j + oldCap\] = hiHead;

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap底层实现原理和扩容机制

一、底层原理 HashMap底层是基于哈希表数组实现的，它依赖hashCode方法和equals方法保证"键"的唯一 jdk1.8之前：数组+链表+头插法 jdk1.

迷南。/ 2024年03月22日 15:40/ 0 赞/ 54 阅读

相关 HashMap的底层原理和扩容机制

一，HashMap的基本数据结构 HashMap继承了Map抽象类，实现了Map，Cloneable，Serializable接口。 1.7 数组 + 链表 1

桃扇骨/ 2024年03月17日 23:20/ 0 赞/ 111 阅读

相关 HashMap的扩容机制原理

1.7 版本 1. ⽣成新数组，是原来数组的2倍 2. 遍历⽼数组中的每个位置上的链表上的每个元素 3. 取每个元素的key，并基于新数组⻓度，计算出每个元素在新数组中

桃扇骨/ 2024年02月05日 22:40/ 0 赞/ 30 阅读

相关 HashMap扩容机制

1. 介绍一下几个名词：容量：capacity ，默认16。加载因子：loadFactor，默认是0.75 阈值：threshold，

╰+哭是因爲堅強的太久メ/ 2023年10月14日 14:11/ 0 赞/ 57 阅读

相关 hashmap 扩容机制

hashmap是一种基于数组和链表（或红黑树）的数据结构，它可以存储键值对的映射关系。hashmap的扩容机制是指当hashmap中的元素个数超过数组长度乘以负载因子时，就会重

逃离我推掉我的手/ 2023年10月10日 21:09/ 0 赞/ 85 阅读

相关 HashMap扩容机制

想要了解HashMap的扩容机制你要有这两个问题 1.什么时候才需要扩容 2.HashMap的扩容是什么 1.什么时候才需要扩容 > 当HashMap

逃离我推掉我的手/ 2023年10月05日 14:41/ 0 赞/ 11 阅读

相关 Java之HashMap系列--HashMap扩容的原理

原文网址：[Java之HashMap系列--HashMap扩容的原理\_IT利刃出鞘的博客-CSDN博客][Java_HashMap_--HashMap_IT_-CSDN]

秒速五厘米/ 2023年10月01日 17:09/ 0 赞/ 13 阅读

相关 HashMap 扩容原理

今天有个朋友问我，为啥hashMap扩容之后数组的位置是当前位置或当前位置 + oldCap 呢？想了一下，举个例子最清楚了我们模拟一下就清楚了，分别用两个k

矫情吗；*/ 2023年01月12日 01:56/ 0 赞/ 175 阅读

相关 HashMap扩容机制

HashMap中的主要参数 = 容量、加载因子、扩容阈值容量 // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进

Myth丶恋晨/ 2022年05月16日 12:18/ 0 赞/ 255 阅读

相关 HashMap的扩容

之前也研究过HashMap的源码，但是对扩容这块没有做过深入的研究。这几天，抽时间看了一下HashMap的resize的源码文章将从下面几个方面对resize方法进行解析

男娘i/ 2021年11月04日 11:12/ 0 赞/ 412 阅读