Java集合08 - JDK1.7中的HashMap

我不是女神ヾ 2022-12-29 12:47 199阅读 0赞

**目录**

1.HashMap是什么

2.HashMap底层实现

3.Hash函数

3.1 Hash()函数在HashMap中的作用

3.2 源码剖析

4.HashMap的扩容机制

5.扩容后的数据迁移

6.put方法流程

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

## 1.HashMap是什么 ##

源码注释告诉我们：

**       底层实现**：基于Map接口实现的key-value存储结构，允许null键和null值，无序（无论是元素添加顺序还是元素a~z的自然排序顺序）。

**       扩容机制：**初始容量和负载因子是影像HashMap性能的两个参数，不要将初始容量设置得太高（或者负载系数设置太低）。当HashMap容量大于等于加载因子与当前容量的乘积时，HashMap将会重建内部结构，进行2倍扩容，建议在创建HashMap实例的时候指定初始容量，以便减少rehash的次数。

**同步机制：**HashMap的实现是不同步的，如果多个线程同时访问HashMap实例，并且至少有一个线程在结构上进行了修改，则必须在外部同步。（结构修改是指添加、删除一个或多个元素，或显式调整底层储存数组容量的操作；仅仅设置元素的值不是结构修改），这通常是通过在HashMap实例对象上进行同步来实现。 如果不存在这样的对象，应使用Collections.synchronizedMap(new HashMap(...))来创建线程同步的集合。

**fail-fast特性：**迭代器为快速失败，用增强for/迭代器遍历HashMap时，迭代器的remove()和add()可能会抛出ConcurrentModificationException异常，迭代器的fail-fast行为在不同步的并发修改时不能得到硬性保证，fail fast行为应仅用于检测错误，不要依赖此异常进行编程。

## 2.HashMap底层实现 ##

可以看到源码中定义了一个数组：

![20201222212231152.png][]

数组存放的是HashMap中一个叫Entry内部类：

![20201222212409217.png][]

看起来非常像单链表的基本结构，只不过多了一个hash字段，没错在JDK1.7中，HashMap就是由数组加链表来作为基本存储结构的，如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70][]

图片借鉴自：[https://www.pianshen.com/article/7278201811/][https_www.pianshen.com_article_7278201811]

我们可以从上图看到，左边是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。

## 3.Hash函数 ##

### **     3.1 Hash()函数在HashMap中的作用** ###

**       **先了解以下三个概念：

**       Hash函数：又叫"散列函数"，是把任意长度的输入转换成固定长度输出的一种压缩算法**（HashMap中需要根据元素特征计算元素数组下标）

**       散列函数的特性：同一散列函数计算出的散列值如果不同，那么输入值肯定不同；同一散列函数计算出的散列值如果相同，输入值不一定相同。**

**       ****Hash碰撞：两个不同的输入值，根据同一散列函数计算出相同的散列值。**

**       **在JDK1.7中主要被引用在如下地方：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1][]

**       **可以看到主要应用在put和remove方法内，因为在增加和删除的时候我们要确定元素的位置，而hash()函数就是起到根据Key来定位其在HashMap中的位置的作用

### **     3.2 源码剖析** ###

**       **源码举例（大家只关注红框里面的内容即可，红框外的下面会说到）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2][]

**       **首先我们需要把Object类型的数据转换成一个整数，所以在hash函数中先调用了key的hashCode方法，接下来就是用h ^ k.hashCode()，这个h可以看到是由hashSeed赋值来的，这个hashSeed又是什么呢？这里买个坑，下面会说这个问题，先把h的默认成0，进行按位异或即可。接下来可以看到又将h的值进行了九次扰动计算（四次位运算+五次异或运算），**为什么JDK1.7在计算完对象的hashCode()之后还要进行九次扰动计算呢？**源码上的注释机翻一下为：此函数可确保在每个位位置仅相差常量倍数的哈希码具有有限数量的冲突（在默认加载因子下大约为8），简单点说，**就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，尽量做到任何一位的变化都能对最终得到的结果产生影响**。举个例子来说，我们现在想向一个HashMap中put一个K-V对，Key的值为“hollischuang”，经过简单的获取hashcode后，得到的值为“1011000110101110011111010011011”，如果当前HashTable的大小为16，即在不进行扰动计算的情况下，他最终得到的index结果值为11。由于15的二进制扩展到32位为“00000000000000000000000000001111”，所以，一个数字在和他进行按位与操作的时候，前28位无论是什么，计算结果都一样（因为0和任何数做与，结果都为0），如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3][]

**       **可以看到，后面的两个hashcode经过位运算之后得到的值也是11 ，虽然我们不知道哪个key的hashcode是上面例子中的那两个，但是肯定存在这样的key，这就产生了冲突。那么接下来看一下经过扰动的算法最终的计算结果会如何：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4][]

**       **从上面图中可以看到，之前会产生冲突的两个hashcode，经过扰动计算之后，最终得到的index的值不一样了，这就很好的避免了Hash冲突。那么**为什么可以使用位运算代替取模运算呢？**

**       X % 2^n = X & (2^n - 1)：**2^n表示2的n次方，也就是说一个数对2^n取模 == 一个数和(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，也就是余数。

**       **那么**为什么要使用位运算代替取模运算呢？**

**   ** （1）位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。  
    （2）其实使用位运算代替取模运算除性能之外，还有一个好处就是可以很好的解决负数的问题。因为我们知道，hashcode的结果是int类型，而int的取值范围是-2^31 ~ 2^31 - 1，即\[ -2147483648, 2147483647\]；这里面是包含负数的，我们知道，对于一个负数取模还是有些麻烦的。如果使用二进制的位运算的话就可以很好的避免这个问题。首先，不管hashcode的值是正数还是负数。length-1这个值一定是个正数。那么，他的二进制的第一位一定是0（有符号数用最高位作为符号位，“0”代表“+”，“1”代表“-”），这样里两个数做按位与运算之后，第一位一定是个0，也就是，得到的结果一定是个正数。

## 4.HashMap的扩容机制 ##

了解扩容机制之前，我们需要先了解一下HashMap中三个重要的成员变量：

**transient int size：**记录了存入HashMap中Value的个数

**final float loadFactor：**装载因子，用来衡量HashMap满的程度，loadFactor的默认值为0.75

** int threshold：**临界值，当实际Value个数超过threshold时，HashMap会触发扩容，threshold＝容量\*装载因子

添加节点源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5][]

我们可以看到先判断了一下HashMap中元素个数是否超过临界值，并且当前数组位置不能为空（为空的话放到当前位置就可以了），就会触发扩容机制，为当前数组长度的2倍扩容，resize()源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6][]

可以看到首先判断了老数组长度是否等于最大容量（**为什么不是大于等于呢？****前面说扩容为2倍扩容，那么不管怎么扩都会是2的倍数，也就不会出现大于最大容量的情况了**），接下来调用了transfer(newTable, initHashSeedAsNeeded(newCapacity));那么这个**transfer函数是做什么的呢？****前面我们对数组的容量直接进行了扩容，但仅仅扩大数组容量还不够，还需要对原数组中的数据进行重新迁移，这就是transfer函数的作用。****那么为什么要迁移呢，放在原位置不行么？****HashMap性能指标中很重要的一点是，要保证散列值的均匀分布，避免同一个桶中出现过长数据链。不重新进行数据迁移的话，大多数据都集中在原数组前半段，会大大增加Hash碰撞的几率。**接下来跟进transfer方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7][]

我们先默认另一个入参参数rehash是false，这样的话，就变成了遍历数组中所有Entry节点，并且用头插法实现的数据迁移（后三行不懂的小伙伴拿张纸画一下就懂了）。接下来就是填一下在hash()函数中埋下的坑，**hashSeed和initHashSeedAsNeeded()函数是什么？****hashSeed可以把它看成一个开关，如果开关打开，并且key的类型是String时可以采取sun.misc.Hashing.stringHash32方法获取其hash值。而initHashSeedAsNeeded()方法：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8][]

从上图代码可以看到，hashSeed的计算流程涉及到一个设定值`Holder.ALTERNATIVE_HASHING_THRESHOLD`，该设定值是通过JVM的参数**`jdk.map.althashing.threshold`**来设置的。在JDK1.8中已经移除掉了，所以默认情况下把hashSeed默认成0即可。

## 5.扩容后的数据迁移 ##

具体看下transfer(用于扩容后的数据迁移)方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 10][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 11][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 12][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 13][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 14][]

## 6.put方法流程 ##

1.7的put方法还是比较简单的，笔者这里直接梳理了一份流程图供大家参考：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 15][]

文中部分内容借鉴自：[http://hollischuang.gitee.io/tobetopjavaer/\#/menu][http_hollischuang.gitee.io_tobetopjavaer_menu]，一个非常好的java知识点总结项目。

[20201222212231152.png]: /images/20221120/dd7a119620fd43dfbb6a234a2ba57076.png
[20201222212409217.png]: /images/20221120/b48332664f6748c7814d84c42ca63419.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201222212907582.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[https_www.pianshen.com_article_7278201811]: https://www.pianshen.com/article/7278201811/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201222214450947.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201222215029489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201222220631644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201222220706354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201222221522586.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201222221738131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201222222602166.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201222223138489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201223224335815.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020122322522730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201223225411463.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20201223225602559.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20201223225728558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20201223225845763.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20201227133825468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[http_hollischuang.gitee.io_tobetopjavaer_menu]: http://hollischuang.gitee.io/tobetopjavaer/#/menu