图解集合4：HashMap

旧城等待， 2023-03-13 03:56 9阅读 0赞

**初识HashMap**

之前的List，讲了ArrayList、LinkedList，最后讲到了CopyOnWriteArrayList，就前两者而言，反映的是两种思想：

（1）ArrayList以数组形式实现，顺序插入、查找快，插入、删除较慢

（2）LinkedList以链表形式实现，顺序插入、查找较慢，插入、删除方便

那么是否有一种数据结构能够结合上面两种的优点呢？有，答案就是HashMap。

HashMap是一种非常常见、方便和有用的集合，是一种键值对（K-V）形式的存储结构，下面将还是用图示的方式解读HashMap的实现原理，

每当插入一个元素时，我们都需要计算该值在数组中的位置，即`p = tab[i = (n - 1) & hash]`。

*  使用哈希表（散列表）来进行数据存储，并使用链地址法来解决冲突
 *  当链表长度大于等于 8 时，将链表转换为红黑树来存储（java8）

**四个关注点在HashMap上的答案**

<table> 
 <tbody> 
  <tr> 
   <td><strong>关 &nbsp;注 &nbsp;点</strong></td> 
   <td><strong>结 &nbsp; &nbsp; &nbsp;论</strong></td> 
  </tr> 
  <tr> 
   <td>HashMap是否允许空</td> 
   <td>Key和Value都允许为空</td> 
  </tr> 
  <tr> 
   <td>HashMap是否允许重复数据</td> 
   <td>Key重复会覆盖、Value允许重复</td> 
  </tr> 
  <tr> 
   <td>HashMap是否有序</td> 
   <td>无序，特别说明这个无序指的是<strong>遍历HashMap的时候，得到的元素的顺序基本不可能是put的顺序</strong></td> 
  </tr> 
  <tr> 
   <td>HashMap是否线程安全</td> 
   <td>非线程安全</td> 
  </tr> 
 </tbody> 
</table>

jdk1.8([https://www.jianshu.com/p/b0334fb09fcf][https_www.jianshu.com_p_b0334fb09fcf]) hashmap与jdk之前版本区别

*  HashMap 插入数据时一直是插入到链表表头；而到了 Java 8 之后，则改为了尾部插入。至于头插入有什么缺点，其中一个就是在并发的情况下因为插入而进行扩容时可能会出现链表环而发生死循环
 *  Java8 规定了 HashMap 每次扩容都为之前的两倍（n\*2），也正是因为如此，每个元素在数组中的新的索引位置只可能是两种情况，一种为不变，一种为原位置 + 扩容长度（即偏移值为扩容长度大小）；反观 Java8 之前，每次扩容需要重新计算每个值在数组中的索引位置，增加了性能消耗
 *

[https_www.jianshu.com_p_b0334fb09fcf]: https://www.jianshu.com/p/b0334fb09fcf