Java集合11 - HashMap中一些值得思考的问题

淡淡的烟草味﹌ 2022-12-30 03:37 158阅读 0赞

**目录**

1.Key为null的键值对存储位置

2.为什么重写equals()一定要重写hashCode()

3.为什么HashMap的容量要为2的n次方

4.为什么HashMap的默认负载因子设置成0.75

5.JDK1.7头插法导致的闭环链问题

--------------------

### 1.Key为null的键值对存储位置 ###

JDK1.7存放null值源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70][]

可以看到1.7中将null值存放在数组0号索引处，JDK1.8源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1][]

由于在hash函数中，null的hash为0，所以红框中的代码可以简化成：

if ((p = tab[i = 0]) == null)
        tab[i] = newNode(hash, key, value, null);

可以看到1.8中也是将null值存放在数组0号索引处，综上两种情况，**HashMap将Key为null的键值对存放在数组0号索引处**。

### 2.为什么重写equals()一定要重写hashCode() ###

JDK1.7中put方法部分源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2][]

JDK1.8中put方法部分源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3][]

我们发现两个版本的put方法中对相同Key的判断方式几乎一致，为：**if (e.hash == hash && ((k = e.key) == key || key.equals(k)))，先说结论，如果尝试使用HashMap作为对象的存储结构，那么重写equals()方法时一定要重写hashCode()**。我们可以看到HashMap在判断是否为同一个Key的时候，先判断两者的hash值是否相等(hashCode()为计算hash值的前提)，如果hash值不相等那么两者一定不等。如果我们只重写了equals()而没有重写hashCode()，**就会造成我们主观逻辑上想让HashMap认为两个对象相等，但HashMap自己判断的结果却是不等。**

### 3.为什么HashMap的容量要为2的n次方 ###

JDK1.7中indexFor方法源码(用于将hash函数生成的整型转换成链表数组中的下标)：

![20201223204545391.png][]

JDK1.8：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4][]

可以看到1.7和1.8都采用了相同的方式来计算HashMap数组的下标，那么和HashMap的容量为16有什么关系呢？indexFor方法中的两个参数h表示元素的hashcode值，length表示的就是HashMap的容量。因为java使用位运算(&)来代替取模运算(%)，实现原理为：X % 2^n = X & (2^n – 1)，假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。所以return h & (length-1);只要保证length的长度是2^n 的话，就可以实现取模运算了。**结论：因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高，所以HashMap在计算元素要存放在数组中的index的时候，使用位运算代替了取模运算，而之所以可以做等价代替，前提是要求HashMap的容量一定要是2^n。**

### 4.为什么HashMap的默认负载因子设置成0.75 ###

关于负载因子为0.75在JDK官方文档中写了一段话：“**一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put**”。结合这段话，我们假设把负载因子设为1，在默认容量为16的情况下，必须要数组所有位置填满才能扩容，而随着元素的增多，hash碰撞的几率也在增大；假设把负载因子设为0.5的话，HashMap存储了一半的元素就会进行扩容，实际发生hash冲突的几率很低，这样就打打浪费了空间。所以负载因子设为0.75的答案我想就是这句话，**在时间和空间成本之间提供了很好的权衡。**

### 5.JDK1.7头插法导致的闭环链问题 ###

聊这个问题之前我们先看一下1.7HashMap中的transfer(用于扩容后的数据迁移)方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5][]

重点看红框里的四行代码即可，我们先简单的画一下HashMap数据迁移的步骤，**左图为扩容前，右图为扩容后：**

（1）首先创建e和next两个变量指向当前元素和当前元素后一个元素(假设原数组容量为2，扩容后新数组容量为4)：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6][]

（2）然后通过第一行代码计算出数组下标，再执行e.next = newTable\[i\]：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7][]

（3）再执行newTable\[i\] = e：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8][]

（4）再执行e = next，同时进入下一次循环改变next的指向：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9][]

（5）继续循环下去，假设经过indexFor()函数计算后都保存在了table\[3\]（1.8中就是这样的，要么在原位置，要么在原位置+旧容量）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 10][]

以上就是1.7中HashMap数据迁移的流程，理解这个之后，我们再来看一下在数据迁移的时候到底是怎样形成闭环链的（看下面之前请确保以上步骤完全理解）：

（1）肯定要两个线程才能发生闭环问题，线程1阻塞在这一步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7][]

（2）这时线程2完成了对数据的迁移：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 10][]

（3）唤醒线程1，线程1继续执行，由于操作的都是一个HashMap实例，导致线程1将A元素插入进新数组，从而将线程2的结果覆盖，并且由于这些元素全部存在于堆中(内存的可见性)，导致B元素的指向变成了A：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 11][]

（4）线程1继续将B元素添加进新数组：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 12][]

（5）线程1尝试将A元素添加进新数组时发生如下问题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 13][]

（6）上述这样画只是为了让小伙伴们看清闭环现象，其实这么画是错误的，因为A元素在内存中只有一份，所以正确的图如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 14][]

个人感觉闭环问题是一个比较适合学习多线程的入手问题，代码量不多就三行代码，仔细捋一下流程，画个图出来就懂了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: /images/20221120/9b9156092d92445eb960f78532c25f9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: /images/20221120/7136267d37bf433e963491e5b8d92dae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: /images/20221120/0bd66bcea06a40509eefb4d9f4a6a89e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: /images/20221120/823a8fb98379430bbeff6dd570ae5caf.png
[20201223204545391.png]: /images/20221120/6360549659ba4d0ba300dfa726ac6060.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4]: /images/20221120/59654088ba96461ca591ad32eff47138.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5]: /images/20221120/d1f9b30ef57148dc994618fa9a535abc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6]: /images/20221120/c5af73a02ddb48d6879b25377f5db192.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7]: /images/20221120/a3ee6d10d44f48deb2cca5ab4db20284.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8]: /images/20221120/73c2c01ab8df4c19baad5a2bebe6da28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9]: /images/20221120/c34d4d43a2a647219bcdce3531ad47fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 10]: /images/20221120/37e5e090b2bc4baaadae7c9aef51dc25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 11]: /images/20221120/39d0f80aaed94c198a7b1adc345bd058.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 12]: /images/20221120/97ab2dfa71cf47d88e927987aaa4286c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 13]: /images/20221120/a332e2dc986040b3b7c4aa565bd4d546.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 14]: /images/20221120/15bb95e2eb294887a8ffbd760c672a9f.png