HashMap知识点总结（2）

柔光的暖阳◎ 2022-05-17 00:07 201阅读 0赞

# **HashMap集合知识点总结** #

众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。

HashMap数组每一个元素的初始值都是Null。

对于HashMap，我们最常使用的是两个方法：Get和Put。

1.  **Put方法的原理**

调用Put方法的时候发生了什么呢？

比如调用hashMap.put(“apple”,0)，插入一个Key为”apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）：

index = Hash(“apple”)

假定最后计算出的index是2，那么结果如下：

![70][]

但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样：

![70 1][]

这时候该怎么办呢？我们可以利用**链表**来解决。

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可：

![70 2][]

需要注意的是，新来的Entry节点插入链表时，使用的是“**头插法**”。至于为什么不插入链表尾部，后面会有解释。

1.  **Get方法的原理**

使用Get方法根据Key来查找Value的时候，发生了什么呢？

首先会把输入的Key做一次Hash映射，得到对应的index：

**index = Hash(****“****apple****”****)**

由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是”apple”:

![70 3][]

第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。

第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。

之所以把Entry6放在头节点，是因为HashMap的发明者认为，**后插入的Entry被查找的可能性更大**。

这就是HashMap的底层原理！继续深入问几个问题：

HashMap默认的初始长度是多少？为什么这么规定？

高并发情况下，为什么HashMap可能会出现死锁？

在Java8当中，HashMap的结构有什么样的优化？

**HashMap默认的初始长度是多少？为什么这么规定？**

**答：**HashMap的默认初始长度是16，并且每次自动扩展或是手动初始化时，长度必须是2的幂。之所以选择16，是**为了服务于从Key映射到index的Hash算法**。

之前说过，从Key映射到HashMap数组的对应位置，会用到一个Hash函数：

**index = Hash(****“****apple****”****)**

如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。

如何进行位运算呢？（Key的hash值）与（数组长度-1）进行位与运算，得到对应的数组下标。有如下的公式（Length是HashMap的长度）：

**index = HashCode( Key ) &( Length - 1 )**

下面我们以值为“book”的Key来演示整个过程：

1.  计算book的hashCode，结果为十进制的3029737，二进制的1011100011101011101001。
2.  假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
3.  把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以index = 9。

可以说，Hash算法最终得到的index结果，完全取决于Key的**hashCode值的最后几位**。

这样的方式有什么好处呢？为什么长度必须是16或者2的幂？比如HashMap长度是10会怎么样？

这样做不但效果上等同于取模，而且还大大提高了性能。至于为什么采用16，我们可以试试长度是10会出现什么问题？

假设HashMap的长度是10，重复刚才的运算步骤：

HashCode: 10 1110 0011 1010 1110 1001

Length-1:                      1001

Index:                         1001

**单独看这个结果，表面上并没有问题。我们再来尝试一个新的HashCode:**

101110001110101110**1011**:

HashCode: 10 1110 0011 1010 1110 1011

Length-1:                      1001

Index:                         1001

让我们再换一个HashCode:101110001110101110**1111**试试:

HashCode: 10 1110 0011 1010 1110 1111

Length-1:                      1001

Index:                         1001

是的，虽然HashCode的倒数第二第三位从0变成了1，但是运算结果都是1001。也就是说，当HashMap长度为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）！

这样，显然不符合Hash算法均匀分布的原则。

反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

**问题：为什么HashMap数组默认大小为16，每次扩容必须是2的幂？**

**答：**Key通过Hash算法映射到数组下标index，index = hashCode(Key) & (Length-1)。只有当数组长度为16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

**接下来，我们讲高并发环境下，HashMap可能出现的致命问题。**

在分析高并发场景之前，我们需要先搞清楚\[ReHash\]这个概念。Rehash是HashMap在扩容时候的一个步骤。

HashMap的容量是有限的。当需要的HashMap.size >= Capacity \* LoadFactor时，要进行扩容，扩容分两部分：ReSize和ReHash。

1.  ReSize指的是创建一个新的Entry空数组，长度是原数组的2倍。
2.  ReHash指的是遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

让我们回顾一下Hash公式：

**index = HashCode( Key ) &( Length - 1 )**

当原数组长度为8时，Hash运算是和111B做位与运算；新数组长度为16，Hash运算是和111B做与运算。Hash结果显然不同。

**问：ReHash之后，元素的位置发生了怎样的变化？**

**答：**元素的位置要么在原位置，要么在原位置再移动2次幂的位置。

**注意：在单线程环境下，Rehash过程不会有任何问题，但是HashMap并非是线程安全的，在多线程环境下，Rehash过程会出现问题，什么问题？**

**答：**Rehash在并发的情况下可能会形成**环形链表**。一旦形成环形链表，当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好位于环形链表中的时候，程序将会进入死循环。

**面试题1：HashMap扩容的条件是什么？**

**答：**HashMap.size >= Capacity \* LoadFactor。

**面试题2：**HashMap的扩容包含ReSize和ReHash两个部分，ReSize指的是将创建一个大小为原数组2倍大小的新数组。ReHash指的是遍历原数组，把原数组中所有的Entry重新Hash到新数组。

**如何解决HashMap在高并发环境中的线程安全问题？**

**答：**我们可以采用另一个集合类ConcurrentHashMap。这个集合类兼顾了线程安全和性能。

**问：HashMap是线程安全的吗？**

**答：**HashMap不是线程安全的。在并发插入元素的时候，有可能出现环形链表，让下一次读操作出现死循环。

**问：什么样的数据结构可以即保证线程安全又兼顾性能呢？**

**答：**ConcurrentHashMap。  
**问：在并发环境下，ConcurrentHashMap是怎么保证线程安全的？又是怎么实现高性能读写的？**

**答：不太会，嘿嘿。。。**

**问：没事，回家等通知吧！**

想要避免HashMap的线程安全问题有很多办法，比如改用HashTable或者Collection.synchronizedMap。但是，这两者有着共同的问题：性能。无论读操作还是写操作，它们都会给整个集合加锁，导致同一时间的其他操作为之阻塞。

在并发环境下，如何能够兼顾线程安全和运行效率呢？这时候ConcurrentHashMap就应运而生了。

ConcurrentHashMap的优势就是采用了\[锁分段技术\]，将数据分成一段一段的，每一段称为一个Segment，每一个Segment就好比一个自治区，读写操作高度自治，Segment之间互不影响。

**我们来看一下ConcurrentHashMap读写的详细过程：**

**Get方法：**

1.  为输入的Key做Hash运算，得到hash值。
2.  通过hash值，定位到对应的Segment对象。
3.  再次通过hash值，定位到Segment当中数组的具体位置。

**Put方法：**

1.  为输入的Key做Hash运算，得到hash值。
2.  通过hash值，定位到对应的Segment对象。
3.  获取可重入锁。
4.  再次通过hash值，定位到Segment当中数组的具体位置。
5.  插入或覆盖HashEntry对象。
6.  释放锁。

从步骤可以看出，ConcurrentHashMap在读写时都需要二次定位。首先定位到Segment，之后定位到Segment内的具体数组下标。

**最后还有一个问题：**

既然每一个Segment都各自加锁，那么在调用Size方法的时候，怎么解决一致性的问题呢？

**这个问题问的好！关于这一点，让我们看一看ConcurrentHashMap的Size操作时怎样工作的：**

**ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：**

1.  遍历所有的Segment。
2.  把Segment的元素数量累加起来。
3.  把Segment的修改次数累加起来。
4.  判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是，说明没有修改，统计结束。
5.  如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
6.  再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
7.  释放锁，统计结束。

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。

为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。

**1.HashMap的原理，内部数据结构？**

**答：**底层数据结构为哈希表（数组+链表），当链表过长会将链表转成红黑树以实现O（logN）时间复杂度内查找。

**2.讲一下HashMap中put方法的过程？**

**答：**（1）调key的hashCode()方法计算key的哈希值，然后根据映射关系计算数组下标

（2）如果hash值冲突，调用equal()方法进一步判断key是否已存在

若key已存在，覆盖key对应的value值

若key不存在，将结点链接到链表中，若链表长度超过阈（TREEIFY\_THRESHOLD == 8），就把链表转成红黑树

（3）如果hash值不冲突，直接放入数组中，若数据量超过**容量\*负载因子**，需要对原数组进行扩容，每次扩容2倍

**3.抛开HashMap，hash冲突有哪些解决方法？**

**答：**链地址法、开发地址法、再hash法等。

**4.针对HashMap中某个Entry链太长，查找时间复杂度可能达到O（n），怎么优化？**

**答：**将链表转为红黑树。JDK1.8已经实现。

**5.HashMap怎样解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是怎么定位到这个值新数组中的位置。**

**答：**HashMap解决hash冲突的方法是链地址法，用链表存储hash值相同的元素。

当数据量超过HashMap数组容量的负载因子（默认0.75）之后，就会进行扩容，每次扩容2倍，扩容后会对每个结点重新计算哈希值

这个值可能在两个地方，一个是在原下标的位置，另一个是在下标为<原下标+原容量>的位置。

Map是用来存储键值对的数据结构，在数组中通过数组下标来对其内容索引的，而在Map中，则是通过对象来进行索引的，用来索引的对象叫做key，其对应的对象叫value。

**1. HashMap和Hashtable的区别？**

**答：**Hashtable是线程安全的，效率低，不允许null键null值，Hashtable的hash数组默认大小是11，增加的方式是old\*2+1。

HashMap是Hashtable的轻量级实现，是线程不安全的，效率高，允许null键null值，HashMap的hash数组默认大小是16，增加的方式是old\*2。

**2. 在Hashtable上下文中，同步指的是什么？**

**答：**同步意味着在一个时间点只能有一个线程可以修改hash表，任何线程在执行Hashtable的更新操作前都需要获取对象锁，其它线程则等待锁的释放。

**3. 如何实现HashMap的同步？**

**答：**HashMap可以通过Map m = Collections.synchronizedMap(new HashMap())来达到同步的效果。具体而言，该方法返回一个同步的Map，该Map封装了底层的HashMap的所有方法。

**4. HashMap里面存入的键值对在取出时是有序的还是无序的？**

**答：**无序的。

**5. HashMap中键不可以重复，值可以重复，如果我存入了一个已经存在的键，会怎么样呢？**

**答：**会用该键对应的新值替换掉该键对应的老值，并返回老值。

**6.我们怎样去创建一个Map集合呢？**

**答：**Map<String,String> map = new HashMap<String,String>();

**7.在操作Map集合时，你经常会用到哪几个方法：**

**答：**put(K key,V value):添加元素

get(Object key):根据键获取值

remove(Object key)：根据键删除键值对元素，并把值返回

containsKey(Object key)：判断集合是否包含指定的键

**8.创建一个Map集合，往里面存<String,String>，并将所存数据遍历出来。**

**答：**

<table style="width:426.1pt;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> public static void main(String[] args) { //&nbsp;创建集合对象 HashMap&lt;String, String&gt; hm = new HashMap&lt;String, String&gt;(); &nbsp; //&nbsp;创建元素并添加元素 hm.put("it001", "马云"); hm.put("it003", "马化腾"); hm.put("it004", "乔布斯"); hm.put("it005", "张朝阳"); hm.put("it002", "裘伯君"); // wps hm.put("it001", "比尔盖茨"); &nbsp; //&nbsp;遍历 Set&lt;String&gt; set = hm.keySet(); for (String key : set) { String value = hm.get(key); System.out.println(key + "---" + value); } } </td> 
 </tr> 
 </tbody> 
</table>

**9. HashMap中的键是用什么存储的？**

**答：**是用set集合存储的。

**10. HashMap中的值是用什么存储的？**

**答：**是用Collection集合存储的。

**11. HashMap中的链表中存放的是什么？**

**答：**是哈希地址冲突的不同记录。

**12. HashMap的数组中存放的是什么？**

**答：**是链表的头结点。

**13. HashMap中，定义了一个哈希数组table，它的类型是什么？**

**答：**Entry\[\]。

**14. HashMap中采用什么方法来解决哈希值冲突的问题？**

**答：**链地址法。

**15. HashMap的负载因子默认值是多少？**

**答：**0.75。

**16. HashMap的底层用到了哪两种数据结构？它们分别用来做什么？**

**答：**分别是数组和链表。数组的索引就是对应的哈希地址，存放的是链表的头结点即插入链表中的最后一个元素，链表存放的是哈希地址冲突的不同记录。

**17. 为什么String，Integer这样的wrapper类适合作为HashMap集合的键？**

**答：**因为String和Integer这样的wrapper类是final类型的，具有不可变性，并且已经重写了equals()方法和hashCode()方法。

**18. HashMap中添加元素的操作过程是怎样的呢？（put方法的执行流程）**

**答：**首先，调用key的hashCode()方法生成一个hash值h1，如果这个h1在HashMap中不存在，那么直接将<key,value>添加到HashMap中；如果这个h1已经存在，那么找出HashMap中所有hash值为h1的key，然后分别调用key的equals()方法判断当前添加的key值是否与已经存在的key值相同。如果equals()方法返回true，说明当前需要添加的key已经存在，那么HashMap会使用新的value值来覆盖掉旧的value值；如果equals()方法返回false，说明新增加的key在HashMap中不存在，因此就会在HashMap中创建新的映射关系。

**19. HashMap中获取元素的操作过程是怎样的呢？（get方法的执行流程）**

**答：**从HashMap中通过key查找value时，首先调用的是key的hashCode()方法来获取到key对应的hash值，这样就可以确定键为key的所有值存储的首地址，如果h对应的key值有多个，那么程序接着会遍历所有key，通过调用key的equals()方法来判断key的内容是否相等。只有当equals()方法的返回值为true时，对应的value才是正确的结果。

**20. 在使用自定义类作为HashMap的key时，明明向HashMap中添加的两个键值对的key值是相同的，可是为什么在后面添加的键值对没有覆盖前面的value呢？**

**答：**由于使用自定义的类作为HashMap的key，而没有重写hashCode()方法和equals()方法，默认使用的是Object类的hashCode()方法和equals()方法。Object类的equals()方法的比较规则如下：当参数obj引用的对象与当前对象为同一对象时，就返回true，否则返回false。hashCode()方法会返回对象存储的内存地址。由于在上例中创建了两个对象，虽然它们拥有相同的内容，但是存储在内存中不同的地址，因此在向HashMap中添加对象时，调用equals()方法的返回值为false，HashMap会认为它们是两个不同的对象，就会分别创建不同的映射关系。因此，为了实现在向HashMap中添加键值对，可以根据对象的内容来判断两个对象是否相等，这就需要重写hashCode()方法和equals()方法。

**21. 两个对象相等，那么这两个对象有着相同的hashCode，反之则不成立。**

**22. HashMap的原理是什么呢？**

**答：**HashMap的实现采用了除留余数法形式的哈希函数和链地址法解决哈希地址冲突的方案。这样就涉及到两种基本的数据结构：数组和链表。数组的索引就是对应的哈希地址。存放的是链表的头结点即插入链表中的最后一个元素，链表存放的是哈希地址冲突的不同记录。

**23. HashMap是如何解决添加元素时哈希值冲突问题的？**

**答：**当哈希地址冲突时，HashMap采用了链地址法的解决方式，将所有哈希地址冲突的记录存储在同一个线性链表中。具体来说就是根据hash值得到这个元素在数组中的位置（即下标）。如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。

**24. 如果HashMap的大小超过了负载因子（load factor）定义的容量，怎么办？**

**答：**HashMap默认的负载因子大小为0.75，也就是说，当一个map填满了75%的空间的时候，将会创建原来HashMap大小的两倍的数组，来重新调整map的大小，并将原来的对象放入新的数组中。

[70]: /images/20220517/851cd9ef665c43dfb32b7eb835d1ea5f.png
[70 1]: /images/20220517/b57535f10a4044b9a79478b6d44c3825.png
[70 2]: /images/20220517/8f019e54693145e6908e8731aff46576.png
[70 3]: /images/20220517/fcd3eb3f78a64f29ba48c49d654c0f67.png