0.5、HashMap 的一些基础知识

深藏阁楼爱情的钟 2021-12-21 02:03 276阅读 0赞

### 文章目录 ###

*   *   *   *  前言
             *  磨刀不误砍柴工
             *  标兵就位
             *   *  哈希表（散列表）
                 *  HashMap 的实现是数组+链表+红黑树
                 *  注意区分 数组长度、链表长度、已含元素数量、红黑树节点数量
                 *  键值对被内部封装为 Node < K,V>节点
                 *  数组初始长度为16（1<<4）
                 *  链表转化为红黑树的两个必要条件
                 *  加载因子和扩容条件
                 *  数组扩容的三种情况
                 *  HashMap 确定数组中的位置：hashCode()&（数组长度-1）
                 *  数组必须成倍扩容-即指数增长
                 *  红黑树恢复为链表的条件
                 *  扩容消耗资源为啥不一下申请大一些的资源？

#### 前言 ####

> 体能状态先于精神状态，习惯先于决心，聚焦先于喜好。

#### 磨刀不误砍柴工 ####

> HashMap 的源码是一定要看的，你应该对它在Java 界的地位有所了解，否则你应该不会有兴趣看到我的这篇文章。  
> 本文将就 HashMap 源码阅读前的一些基础知识进行介绍，并且，作为真正进入源码的思路大纲。

#### 标兵就位 ####

##### 哈希表（散列表） #####

> 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。  
> 哈希表的实现方式有很多种，Java 中的 HashMap 就是基于哈希表这种数据结构。  
> [hashCode()][hashCode]就是hashMap 中的初步的散列函数-HashMap对这个函数进行了进一步的封装。

##### HashMap 的实现是数组+链表+红黑树 #####

> 在 jdk 1.7 及以前，HashMap 的实现是：数组+链表。  
> 从 jdk1.8 开始，HashMap的实现是：数组+链表+红黑树，并且，当满足一定条件时，为了提高搜索效率，链表会被转化为红黑树，当满足一定条件时，红黑树也会被转化回链表。  
> 初始化的HashMap 只有一个数组，只有在两个不同的键值对的hash值相同时，即定位到同一个数组位置时，才会产生链表，在链表长度变化时才会在红黑树进行转化。

##### 注意区分 数组长度、链表长度、已含元素数量、红黑树节点数量 #####

> 本条需要对基础概念的了解，建议阅读完本文后再次阅读。  
> HashMap 是基于数组的，这里数组长度就是数组长度，不管数组是否存满了节点。  
> 链表长度是指，数组的每一位可以连接一个链表，从数组节点算起到链表最后一个节点的长度。  
> 已含元素数量，是指HashMap 对象的数组中的节点数量加上非数组部分的节点数量的和。  
> 红黑树节点数量，指链表转化为红黑树后，该红黑树从数组中的一个节点和该节点连接的红黑树的节点的数量之和。

##### 键值对被内部封装为 Node < K,V>节点 #####

> 尽管从外围看，你是以键值对保存数据的，但是在 HashMap 的具体实现上，每一个键值对会被封装到一个 Node 节点里。  
> Node 表示内部类。  
> 此外，Java提供了不止一种 Node 节点，因为不同场景下Node节点需要附带不同的额外信息，比如hash值，上一个节点等等。  
> 比如链表中的节点是 HashMap.Node<K.V> (这里 Node 是 HashMap 内部类)  
> 而在红黑树中的节点是 HashMap.TreeNode<K,V> (这里 TreeNode 是HashMap内部类)

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

##### 数组初始长度为16（1<<4） #####

> 默认初始化的工作并不是在对象实例化时完成的，而是在你向HashMap对象放入第一个键值对时。  
> HashMap 默认初始化只有一个 Node< K,V>类型 数组，尚不包含链表。  
> 如果你不通过构造方法指定数组初始长度的话，那么默认的数组长度是16，即1<<4。

##### 链表转化为红黑树的两个必要条件 #####

> jdk1.7 不存在红黑树。  
> jdk1.8开始，链表有可能被转化为红黑树，需满足两个条件：  
> 条件1：该链表节点数增加到8  
> 条件2：`数组`长度大于64  
> 源码的逻辑是，如果满足条件一，但是不满足条件2，那么会引起扩容，扩容会引起重 hash

##### 加载因子和扩容条件 #####

> 加载因子是一个小数，默认是 0.75  
> `数组长度 * 加载因子`乘积结果会被 HashMap 对象保存为一个变量，作为下一次扩容的标准——扩容阈值 threshold。  
> 比如数组长度是 16，加载因子是 0.75，那么当`map`中包含元素数量`大于`  
> `16 * 0.75=12`时，就会引起数组扩容。

> 当然，加载因子相关的扩容只是情况的一种，还有一种和链表转红黑树条件不满足有关，即本文的 **链表转化为红黑树的两个必要条件**。

> 这里需要注意的是，通过加载因子引发扩容时比较的是 `HashMap 对象`内保存的所有非空节点数，其由 size 这个参数记录。在红黑树判断引发扩容时，是以`数组长度`大于64作为判断标准的。

##### 数组扩容的三种情况 #####

> 第一种:HashMap 对象的 数组 为空，在放入第一个元素时触发扩容

> 第二种:上面 **加载因子和扩容条件** 已经阐述了第一种引发扩容的情况

> 第三种:和红黑树有关 也已经在上面阐述 **链表转化为红黑树的两个必要条件** 当量表长度满足要求但是数组长度不满足要求时，链表不会转化为红黑树，而是会引起扩容

##### HashMap 确定数组中的位置：hashCode()&（数组长度-1） #####

> 数组长度为2的指数倍，比如十进制16=二进制10000 ，`数组长度-1`用二进制表示就是`(10000-1)=1111`，&运算的结果必然是得到一个整数，其范围在 1111 之内，位运算是很快的哦。  
> 其他2的指数倍的作为数组长度的规律如上，这里不再赘述。

##### 数组必须成倍扩容-即指数增长 #####

> HashMap 对 hashCode()进行了二次封装，并且实用 数组长度-1 和 hashCode()结果与运算，因为数组长度为2的指数倍数，则数组长度-1形式为 1111 这种，hashCode()与运算结果必然对应数组的某一个位置，位运算是很快的

##### 红黑树恢复为链表的条件 #####

> 当删除节点，并且红黑树节点数量减少为6时，红黑树恢复为链表。

##### 扩容消耗资源为啥不一下申请大一些的资源？ #####

> 虽然扩容消耗资源，但是你也不能浪费内存空间呢。毕竟HashMap没有缩容机制，一旦申请了一个较大的数组长度，那么只要这个对象存在，这块内存就一定会被占用的。

[hashCode]: https://blog.csdn.net/bestcxx/article/details/93994371
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70]: /images/20211221/8bc50ff865174009ad92a2f84a51f0a7.png