对Java中HashMap的理解与总结

爱被打了一巴掌 2022-12-10 08:42 141阅读 0赞

### 文章目录 ###

*   *   *   *  前言
             *  JDK1.8版本的HashMap
             *  JDK1.7版本的HashMap
             *  HashMap的扩容机制
             *  总结
             *  参考

#### 前言 ####

从名字来看，HashMap 就是使用Hash值来当map的实际存储key。

需要注意的是，HashMap有两个版本需要甄别，分别是JDK1.8和JDK1.7。

#### JDK1.8版本的HashMap ####

主要是数组+链表+红黑树，但是当链表长度过大时，为了提高效率，会将链表转换为红黑树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center]  
通过下图配合汉语注释，我们看看HashMap中的final变量参数。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 1]

在JDK1.8版本的HashMap中，链表结点元素叫做Node  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
Put方法如下

那么put方法的流程如下:

1.  判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
2.  根据当前 key 的 hashcode定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。 如果当前桶有值（ Hash冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8步的时候会统一进行赋值及返回。 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。 如果是个链表，就需要将当前的 key、value封装成一个新节点写入到当前桶的后面（形成链表）。
3.  接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
4.  如果在遍历过程中找到 key 相同时直接退出遍历。 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
5.  最后判断是否需要进行扩容。

另外假如来了一个元素，该把该元素放到数组的哪个位置呢？这个位置除了与计算后的hash值有关，还与数组的长度有关，下图的n就是数组的长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 4]  
上图的hash通过下面方法算出  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 5]

（1）首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。

（2）在putVal源码中，我们通过(n-1)&hash获取该对象的键在hashmap中的位置。（其中hash的值就是（1）中获得的值）其中n表示的是hash桶数组的长度，并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算。

我们上面提到了，当链表元素过多时，链表会转化为红黑树，下面就是红黑树的定义

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 6]  
作为一个Map,有put方法，也有get方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 7]  
当链表长度大于8，hash桶大于64时，会转换到红黑树。

当红黑树结点数量小于等于6时，会从红黑树转换回去单链表。

#### JDK1.7版本的HashMap ####

HashMap是`数组+链表`，通俗点讲就是数组里放链表，学过数据结构的，链表中放的是Key-Value，链表元素叫做Entry.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvc2hpbWF4aWFvMQ_size_16_color_FFFFFF_t_70_pic_center]

在put元素时，按照`哈希码&(数组元素-1)`,计算应该放到哪个链表里。

当size大于阈值时会将数组扩容，扩容到原来的两倍，将旧数组里的元素全部重新计算下标放到新数组中。

#### HashMap的扩容机制 ####

HashMap有**负载因子0.75和初始容量16**，同时有对应的阈值16\*0.75=12。

当存放的数据长度到12时，会进行**扩容**，大小为原来的**两倍**。扩容首先创建一个新的、存放数据用的数组，再进行rehash，即再次通过哈希散列将数据放到新数组中。之所以要进行rehash，是因为Hash的公式是与长度有关的，如果不重新hash，以后计算Hash就对不上了。

#### 总结 ####

总体来说，JDK1.8版本相对于前面版本的HashMap进行了优化。

在JDK1.7中，插入结点使用头插法，在1.8后，将头插法改成了尾插法。

这么做的原因在于头插法会出现环形链表，导致死循环。

#### 参考 ####

[https://my.oschina.net/crossoverjie/blog/1861138][https_my.oschina.net_crossoverjie_blog_1861138]

[JDK1.8中的HashMap实现][JDK1.8_HashMap]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/46ea19d301594793ba52093933533708.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/bb974331990e495fabdb87adbe87a876.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/72b729e7660b4125b977126c167ef229.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/8209cd724bfd47d99aae52c47a42b7fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/3f8f1dc54a36468ca0d5099a5c9fb032.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/3341b3c8be29444888d638bc22bc8fc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/5903ec6284c74fe7bbfbdf4b694057ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/68e83458f74a4e049511816625b68e90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvc2hpbWF4aWFvMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/cdee5413e6194de18666a32da0e974ca.png
[https_my.oschina.net_crossoverjie_blog_1861138]: https://my.oschina.net/crossoverjie/blog/1861138
[JDK1.8_HashMap]: https://www.cnblogs.com/doufuyu/p/10874689.html