Hashmap底层解析.面试连环问 | 大别山码将

淡淡的烟草味﹌ 2022-09-13 04:28 159阅读 0赞

#### **@Hashmap？ hashmap 线程安全吗？能变成线程安全吗？不安全，会出现什么现象？** ####

**HashMap基于Map接口实现，元素以键值对的方式存储**，并且允许使用null 建和null值，因为key不允许重复，因此只能有一个键为null,另外**HashMap不能保证放入元素的顺序，它是无序的。HashMap是线程不安全的。多线程环境中推荐ConcurrentHashMap。**

**JDK1.8之前：**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7FzC1CVt-1632738016359)(C:\\Users\\LENOVO-LX\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210902110043071.png)\]][img-7FzC1CVt-1632738016359_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902110043071.png]

HashMap 底层数据结构是 **数组和链表**也就是 散列表，它整合了数组的快速索引和链表的动态扩容这两种数据结构的优势\*\*。初始状态是一个长度为16的数组，每个元素存储的是一个链表的头结点\*\*。

**判断元素存放的位置**一般情况是通过hash(key.hashCode())%length获得，也就是**元素的key的哈希值对数组长度取模得到或者hash&(length-1)**。（**hash能把把任意长度数据的输入，通过hash算法变成固定长度的输出。hash算法的执行效率要更高效**）（比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。）**但计算时可能会遇到哈希冲突，也就是不同元素计算出的hash值是一样的，也就是它们在数组的同一个位置，这时候则将冲突的值加到该位置数组的链表中即可。**

> **判断当前元素存放的位置（也就是对应的数组下标）一般情况是通过hash%length也就是元素的key的哈希值对数组长度取模得到，注意：计算时要让key的hash值高16位也参与路由运算，因为当数组的长度length很短时，只有低位数的hashcode值能参与运算。而让高16位参与运算可以更好的均匀散列，降低hash冲突的几率，让 HashMap 存取⾼效**。
> 
> **实际中我们一般使用hash&(length-1)进行元素位置计算，因为计算机中直接求余效率不如位移运算&**，要想保证**hash%length==hash&(length-1)**，那么**length**必须是**2的n次方**，这也解释了HashMap的长度为什么是2的幂次方的问题

**发生冲突时会形成链表，当链表⻓度⼤于阈值（默认为 8），并且数组长度超过64个时，那么这个链表就会树化成红黑树**，**因为当出现由于哈希冲突导致形成的链表链化链得很长的的时候，hashMap的查找速度就从O(1)升到O(n)，违背了我们使用数组+链表提高查询效率的初衷，而红黑树是一个自平衡的二叉查找树，可以提高查询效率**。所以hashmap底层结构其实是数组+链表+红黑树；**而当数组长度并未超过64个时就选择对数组进行扩容，数组默认长度为16，把数组长度扩大，桶位多了，每个桶位存放的链表长度就减少了，那么查询的效率就会提升；**

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

**HashMap多线程操作导致死循环问题**：

主要原因是多线程情况下数组进行**put操作**，如果数组的长度不够， 那么这时候HashMap就会进行Rehash操作，两个线程在这个时候很有可能同时触发了rehash操作，造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使⽤ HashMap,因为**多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失**。所以为什么并发环境下推荐使⽤ ConcurrentHashMap 。  
**ConcurrentHashMap线程安全的具体实现（底层实现）**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JlvFzOMY-1632738065197)(C:\\Users\\LENOVO-LX\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210902125331698.png)\]][img-JlvFzOMY-1632738065197_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902125331698.png]

**JDK1.7:**

① 在 JDK1.7的时候，**ConcurrentHashMap （分段锁）**

**JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组+链表** 实现，JDK1.8采⽤数组+链表/红⿊树。**对整个桶数组中的数据进⾏分割分段( Segment )，然后给每⼀段数据配⼀把锁**，当⼀个线程占⽤锁访问其中⼀个段数据时，其他段的数据也能被其他线程访问。就不会存在锁竞争，提⾼了并发访问率。

**ConcurrentHashMap 是由 Segment 数组结构和HashEntry 数组结构组成。**

**⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组**。 Segment 的结构和 HashMap 类似，是⼀种**数组和链表结构**。**⼀个 Segment 包含⼀个 HashEntry 数组**，每个 HashEntry 是⼀个链表结构的元素，⽤于存储键值对数据。Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。**当对 HashEntry 数组的数据进⾏修改时，必须⾸先获得对应的 Segment 的锁。**

**JDK1.8:**

**ConcurrentHashMap 取消了 Segment 分段锁，底层结构采用数组+链表/红⿊⼆叉树，采⽤ CAS 和 synchronized 来保证并发安全。**。Java 8 在链表⻓度超过⼀定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为\*\*红⿊树（寻址时间复杂度为 O(log(N))）\*\*synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

#### HashMap和HashTable区别 ####

1.  **线程是否安全：** \*\*HashMap 是⾮线程安全的， HashTable 是线程安全的,\*\*因为 HashTable 内部的⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ConcurrentHashMap 吧！）；
2.  **效率：** 因为线程安全的问题， HashMap 要⽐ HashTable 效率⾼
3.  **对** **Null key** **和** **Null value** **的⽀持：** \*\*HashMap 允许有 null 键和 null 值；\*\*HashTable 不允许有 null 键和 null 值，否则会抛出NullPointerException 。
4.  **初始容量⼤⼩和每次扩充容量⼤⼩的不同 ：** ① 创建时如果不指定容量初始值， **Hashtable默认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1**。 **HashMap 默认的初始化⼤⼩为 16**。**之后每次扩充，容量变为原来的 2 倍**。② 创建时如果给定了容量初始值，那么Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩
5.  **底层数据结构：** JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制
6.  **是否有 contains 方法**：**HashMap 没有 contains 方法**；Hashtable 包含 contains 方法，类似于 containsValue。
7.  **父类不同**：**HashMap 继承自 AbstractMap**；Hashtable 继承自 Dictionary。

#### HashMap和HashSet区别 ####

如果你看过 HashSet 源码的话就应该知道： HashSet 底层就是基于 HashMap 实现的。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BxExhcje-1632738191950)(C:\\Users\\LENOVO-LX\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210902102656030.png)\]][img-BxExhcje-1632738191950_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902102656030.png]  
![在这里插入图片描述][bb81a532efba4097bf0e6ba5c47f27e2.gif_pic_center]

[img-7FzC1CVt-1632738016359_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902110043071.png]: /images/20220828/d87f3ee06c4a4968bada1bd31209916d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5aSn5Yir5bGx56CB5bCG_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ba75ffb0a4b2401cbfed1a8d2033f4e1.png
[img-JlvFzOMY-1632738065197_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902125331698.png]: /images/20220828/0313e1fffb564e8791636a033295d527.png
[img-BxExhcje-1632738191950_C_Users_LENOVO-LX_AppData_Roaming_Typora_typora-user-images_image-20210902102656030.png]: /images/20220828/798fd82a891d47de8bfda92f25d80897.png
[bb81a532efba4097bf0e6ba5c47f27e2.gif_pic_center]: /images/20220828/670ef38f27a846bca3fe6a20ecd3b82b.png