（新手必看）HashMap是什么？

￡神魔★判官ぃ 2024-03-24 15:01 19阅读 0赞

#### **HashMap（哈希表）底层到底是什么？如何扩容的？它是怎么实现的呢？它是如何扩容的？想了解就进来看看吧** ####

![c5e62fdf9ea84f24864ab545fdbe56d4.gif][]

>  *  **博主简介：努力的打工人一枚**
>  *  **博主主页：[@xyk：][xyk]**
>  *  **所属专栏: [JavaEE初阶][JavaEE]**

##  ##

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

**目录**

一、哈希表的概念

二、哈希表的一些参数

默认初始容量为16

最大长度为2的30次幂

默认加载因子为0.75

当链表节点小于等于6，自动退化成链表

当链表节点大于等于8，长度大于64时进行变化成红黑树

扩容阈值，当你的hashmap中的元素个数超过这个阈值，便会发生扩容

threshold = capacity \* loadFactor

2.1无参构造函数

三、哈希表扩容机制

3.1到底什么时候扩容？

3.2为什么HashMap的长度必须是2的n次幂

3.3为什么HashMap的键值可以设为null？

3.4为什么不直接取余，而要>>>16？

四、JDK1.8的新结构——红黑树

五、HashMap扩容操作是尾插还是头插？

六、HashMap是怎么解决哈希冲突的？

6.1闭散列

6.2二次探测

6.3开散列/哈希桶

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

## **一、哈希表的概念** ##

> 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2 N)，搜索的效率取决于搜索过程中元素的比较次数

> 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

> 当向该结构中：
> 
>  *  插入元素：Key-Value
> 
> 根据待插入元素的关键码Key，以此函数计算出该元素的存储位置并按此位置进行存放
> 
>  *  搜索元素：Key-Value
> 
> 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功Value

> 在JDK1.7中，HashMap数据结构为数组+链表；JDK1.8之后增加了数组+链表+红黑树变换，HashMap存储的键值对Key-Value，Key具有唯一性，采用了链地址法来处理哈希冲突，当往 HashMap 中添加元素时，会计算 key 的 hash 值取余得出元素在数组中的的存放位置。

> HashMap 是线程不安全的
> 
> 在 1.8 版本的中 hash() 和 resize( ) 方法也有了很大的改变，提升了性能
> 
> Key和Value都可存放null，Key只能存放一个null

![62335ed9f4114d7ca74765ae5be8ed55.png][]

## **二、哈希表的一些参数** ##

![dc027b03b8d64605bc6cd6761339567f.png][]

//HashMap的默认初始长度16
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    	
    	//HashMap的最大长度2的30次幂
    	static final int MAXIMUM_CAPACITY = 1 << 30;
    	
    	//HashMap的默认加载因子0.75
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
    	
    	//HashMap链表升级成红黑树的临界值
    	static final int TREEIFY_THRESHOLD = 8;
    	
    	//HashMap红黑树退化成链表的临界值
    	static final int UNTREEIFY_THRESHOLD = 6;
    	
    	//HashMap链表升级成红黑树第二个条件：HashMap数组(桶)的长度大于等于64
    	static final int MIN_TREEIFY_CAPACITY = 64;

![2ad08c4b12924998bdb8f1f3119f7a27.png][]

### `` ###

> 1.  #### ``默认初始容量为16 ####
> 2.  #### 最大长度为2的30次幂 ####
> 3.  #### 默认加载因子为0.75 ####
> 4.  #### 当链表节点小于等于6，自动退化成链表 ####
> 5.  #### 当链表节点大于等于8，长度大于64时进行变化成红黑树 ####
> 6.  #### 扩容阈值，当你的hashmap中的元素个数超过这个阈值，便会发生扩容 ####
> 7.  #### threshold = capacity \* loadFactor ####

#### 2.1无参构造函数 ####

![2aa55418a93c4298828341096d33ecf3.png][]

>  **可以看到这里只有初始化了负载因子为0.75，还没有初始化容量，阈值也为0**

> 在第一次put时，进行第一次resize！！！

![3b5ce60b7517486ab54950cb3b66ef94.png][]

>  **进入resize中进入分支：**

![232b194f1f154c9485abc3f75b8bb4a6.png][]

> **所以容量cap为默认值16，阈值threshold为 16\*0.75=12。**

## 三、哈希表扩容机制 ##

#### 3.1到底什么时候扩容？ ####

> 其中initailCapacity是初始容量：默认值为16
> 
> 在计算存入结点下标时，会利用 key 的 hsah 值进行取余操作，而计算机计算时，并没有取余等运算，会将取余转化为其他运算；当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高，所以为了提高查询的效率，就要对HashMap的数组进行扩容；

> 那么HashMap什么时候进行扩容呢？
> 
> 当hashmap中的元素个数超过数组大小\*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16\*0.75=12的时候，就把数组的大小扩展为2\*16=32

>  *  当put时发现table未初始化时，进行初始化扩容
>  *  当put加入节点后，发现size（键值对数量）> threshold时，进行扩容 
>  *  而在之后的每次扩容中，容量和阈值都变为原来的两倍
>  *  即两者仍然保持着0.75的比例

![c9652ffa6c8a4c69b42950df02d0ec08.png][] ![367151c4b9df4cf986c03408d83b580c.png][]

![02bf23d1c5f6427b905732c1b6dcd113.png][]

>  **在put方法调用putVal，putVal()再次调用resize()方法**

#### 3.2为什么HashMap的长度必须是2的n次幂 ####

> **1.为了避免哈希碰撞**
> 
> 1.  可以看到HashMap在扩容时选择了位运算，向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置；
> 2.  这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞
> 
> **2.源码解析如下：**

> 1.当HashMap的容量是16时，它的二进制是10000，(n-1)的二进制是01111；
> 
>  *  不同的hash值，和(n-1)去进行&运算，得到的结果是不一样的，使得添加的元素能够均匀分布在集合中不同的位置上，避免hash碰撞；
>  *  如果不是2的n次幂容量，添加元素会导致生成一样的哈希值，严重hash碰撞，导致某一个链表的长度特别长，影响查询的效率；

![a1611b06eb6042999ca1b9dee8d140d2.png][]

![44d18f20cdf14486aa959506550d83f9.png][]

> 2.构造函数给定容量后进行的运算

![38fb764ab96e4e918ce4d9a06f606d3d.png][]

![320a582dce26402394b1eeb8f67617e4.png][]

上面这个方法我来举个例子：

1.当传入的cap值为35时；
    2.首先执行第一步 cap-1，得到n的值为34；
    3.执行第二部：n或（n右移一位），34 二进制为：100010，n右移一位变成：010001，或操作结果为：110011；
    4.n右移两位变成：001100，再与110011进行或操作，变成111111，此时n为111111；
    5.n右移四位变成：000000，再与111111进行或操作，结果n仍为：111111；
    6.n右移16为，再与111111进行或操作，n仍为111111；
    7.n+1变成1000000，变成64；

#### 3.3为什么HashMap的键值可以设为null？ ####

> 因为hashMap在对键值为空的时候做了处理： 当key为空时，哈希值时会直接被赋值为0

![629797862e794a83b00f0d9330663500.png][]

#### 3.4为什么不直接取余，而要>>>16？ ####

> 1.  如果使用直接使用hashCode对数组大小取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的
> 2.  (h >>> 16)是无符号右移16位的运算，左边补0，得到 hashCode 的高16位，可以使得到的 hash 值更加散列，尽可能减少哈希冲突，提升性能
> 3.  而这么来看 hashCode 被散列 (异或) 的是低16位，而 HashMap 数组长度一般不会超过2的16次幂，那么高16位在大多数情况是用不到的，所以只需要拿 key 的 HashCode 和它的低16位做异或即可利用高位的hash值，降低哈希碰撞概率也使数据分布更加均匀

## 四、JDK1.8的新结构——红黑树 ##

> 为了解决JDK1.7中的死循环问题， 在jDK1.8中新增加了红黑树，即在数组长度大于64，同时链表长度大于8的情况下，链表将转化为红黑树。同时使用尾插法。当数据的长度退化成6时，红黑树转化为链表。

![86db184cfb154b17a5edacf2d118f604.png][]

具体讲解以后会讲

## 五、HashMap扩容操作是尾插还是头插？ ##

> JDK1.7扩容：
> 
> **条件**：发生扩容的条件必须同时满足两点
> 
> 1.  当前存储的数量大于等于阈值
> 2.  发生hash碰撞
> 
> 1.  **特点：**先扩容，再添加（扩容使用的头插法）
> 2.  **缺点：**头插法会使链表发生反转，多线程环境下可能会死循环
> 3.  **扩容之后对table的调整**：table容量变为2倍，所有的元素下标需要重新计算

> JDK1.8扩容：
> 
> **条件**：
> 
> 1.  当前存储的数量大于等于阈值
> 2.  当某个链表长度>=8，但是数组存储的结点数size() < 64时
> 
> 1.  **特点**：先插后判断是否需要扩容（扩容时是尾插法）
> 2.  **缺点**：多线程下，1.8会有数据覆盖
> 3.  **扩容之后对table的调整：**table容量变为2倍，但是不需要像之前一样计算下标，只需要将hash值和旧数组长度相与即可确定位置

## 六、HashMap是怎么解决哈希冲突的？ ##

#### 6.1闭散列 ####

> 1.闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

![2e000e47081a46f6995af8341a8986cc.png][]

> 比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突  
> 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

> **采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素**

#### 6.2二次探测 ####

> 线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i平方）% m 或者 Hi = (H0 - i平方）% m

![9b77a033f61646458c2ff696f30e1fbf.png][]

#### 6.3开散列/哈希桶 ####

> **开散列法又叫链地址法(开链法)**，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

![a25e334636254d2ca70ff609629045b7.png][]

##  ##

[c5e62fdf9ea84f24864ab545fdbe56d4.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/908058383c854f6e819b363be8a705b7.png
[xyk]: https://blog.csdn.net/asad21654864?spm=1000.2115.3001.5343
[JavaEE]: https://blog.csdn.net/asad21654864/category_12243955.html?spm=1001.2014.3001.5482
[62335ed9f4114d7ca74765ae5be8ed55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/69ad7dccb5384d47b03e5407787a22ff.png
[dc027b03b8d64605bc6cd6761339567f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d8f8811c745b43d3a2dabad1dad3d86e.png
[2ad08c4b12924998bdb8f1f3119f7a27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6b22555b3c844620b3073cdc4ff4aa30.png
[2aa55418a93c4298828341096d33ecf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3f10f80407804042b47098a78db8884f.png
[3b5ce60b7517486ab54950cb3b66ef94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/13318bafbfaf4eeebf4548d888949afe.png
[232b194f1f154c9485abc3f75b8bb4a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ba46fde8f40d4ab7b5767f0feb79382b.png
[c9652ffa6c8a4c69b42950df02d0ec08.png]: https://img-blog.csdnimg.cn/c9652ffa6c8a4c69b42950df02d0ec08.png
[367151c4b9df4cf986c03408d83b580c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/04376c1046a7423bb0a648d90e9fe698.png
[02bf23d1c5f6427b905732c1b6dcd113.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/27f94eeeb29941239ef2017b261a33b8.png
[a1611b06eb6042999ca1b9dee8d140d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/deeb0419fab2439b8938b3851c43f0c7.png
[44d18f20cdf14486aa959506550d83f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/718d152d865d441c8861653f6b216b7d.png
[38fb764ab96e4e918ce4d9a06f606d3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/948d9394eb9f4f088353c34f335b73b2.png
[320a582dce26402394b1eeb8f67617e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3835eb3a2a014d91a91c7b475b363abf.png
[629797862e794a83b00f0d9330663500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/510bb011a79c445593fdb86f1f58530b.png
[86db184cfb154b17a5edacf2d118f604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c2fa3641dd724532a2488c8788b7a838.png
[2e000e47081a46f6995af8341a8986cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d73cac7cccfb43bfbf4a48d2bee14343.png
[9b77a033f61646458c2ff696f30e1fbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a7fbee2cd8bf4d9bafd7ebb1442e5079.png
[a25e334636254d2ca70ff609629045b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6ba20322ba824ad2b0d76bd4c353a66c.png