详细介绍了HashMap，包括jdk不同版本的升级以及底层的源码分析

小鱼儿 2024-04-05 06:25 152阅读 0赞

### HashMap ###

#### 这里写目录标题 ####

### HashMap概念和背景 ###

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null，此外，HashMap中的映射不是有序的（存储元素和取出元素的顺序有可能不一致）。

数组：查询速度快，可以根据索引查询；但插入和删除比较困难

链表：查询速度慢，需要遍历整个链表，但插入和删除操作比较容易。

HashMap底层是一个hash表（数组+链表），这种结构集合了数组和链表的好处 。

### HashMap的组成结构 ###

<table> 
 <thead> 
  <tr> 
   <th>JDK版本</th> 
   <th>实现方式</th> 
   <th>节点数&gt;=8</th> 
   <th>节点数&lt;=6</th> 
   <th>链表实现方式</th> 
   <th>多线程死循环问题</th> 
   <th>线程安全</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1.8以前</td> 
   <td>数组+单向链表</td> 
   <td>数组+单向链表</td> 
   <td>数组+单向链表</td> 
   <td>头插法</td> 
   <td>会</td> 
   <td>不安全</td> 
  </tr> 
  <tr> 
   <td>1.8以后</td> 
   <td>数组+单向链表/红黑树</td> 
   <td>数组+红黑树</td> 
   <td>数组+单向链表</td> 
   <td>尾插法</td> 
   <td>不会</td> 
   <td>不安全</td> 
  </tr> 
 </tbody> 
</table>

*  jdk1.8之前HashMap由数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突（两个对象调用的hashCode方法计算的哈希值相同）——不用拉链法（引入链表），会在数组hash值所在的地址（已有元素）按你规定的步长（一般是1），向后找，直至有空位就放入元素
 *  jdk1.8之后由数组+链表/红黑树组成，在解决哈希冲突时，当链表长度大于阈值（或者红黑树边界值，默认为8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。
 *  jdk1.8后再单个数组元素上看，红黑树和链表是不共存的，当是从这个HashMap的角度出发，红黑树和链表是共存的。

注意：将链表转换为红黑树前会判断，即便阈值大于8，但是数组长度小于64，此时并不会将链表转变为红黑树，而是选择进行数组扩容（resize方法）

当数组比较小的时候，尽量避免使用红黑树的结构，因为红黑树也是一个平衡二叉树，我们在使用红黑树的时候，必须等保证这个二叉树的平衡，那么就会伴随着会有很多大量的保持红黑树平衡的操作，比如左旋,右旋等操作，如果数组比较小，且每一个数组对应的链表比较短的时候使用红黑树，与直接查找链表比起来，查询效率还更低。

所以为了综合提高性能和减少搜索时间，链表长度大于8并且数组长度大于64时，链表才转换为红黑树

注意：红黑树的节点(元素)的个小于6个，红黑树就会链表化

问题：jdk8后，为什么HashMap的使用了尾插法

主要是为了安全,防止环化

因为resize的赋值方式，也就是使用了 单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置 ，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

出现了环化，取值就会出现无限循环

![6744d7611631bab4c30b30336788dff6.png][]

使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

![d5193de5678f40724b7a85c1f3a5485f.png][]

### HashMap的PUT原理 ###

HashMap 基于 Hash 算法实现的

当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时，

*  如果散列表为空时，调用resize()初始化散列表
 *  如果没用出现hashcode值相同的key，则直接添加元素到散列表中去
 *  如果出现hashcode值相同的key，此时有两种情况。
    
    (1)如果key相同，则覆盖原始值；
    
    (2)如果key不同（出现冲突），则将当前的key-value放入链表中获取时，直接找到hashcode值对应的下标，在进一步判断key是否相同，从而找到对应值。此时为红黑树结构，则直接用红黑树插入。如果是链表，如果链表长度大于8，且数组大于64，大于则进行转换为红黑树，插入键值对；如果链表长度大于8，数组没有大于64，则调用resize()进行扩容数组后插入，都不满足，直接插入链表

理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

### HashMap源码分析 ###

下面的源码时jdk8版本下的

#### 静态常量 ####

serialVersionUID

序列化版本号

private static final long serialVersionUID = 362498820763181265L;

（1）默认初始容量-必须是2的幂

16位，0000 0001左移4位 0001 0000

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

（2）集合最大容量最大容量。必须是2的幂

static final int MAXIMUM_CAPACITY = 1 << 30;

（3）默认负载因子（0.75）

static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子过大（1）表示数组满了，才扩容，这样避免不了哈希碰撞

负载因子较小（0.5）当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是，此时空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。

0.75的负载因子符合统计学，可以兼容空间利用率和查询效率，还降低了哈希碰撞

（4）红黑树转换相关常量

链表的长度大于等于8

static final int TREEIFY_THRESHOLD = 8;

红黑树元素（节点）小于大于6

static final int UNTREEIFY_THRESHOLD = 6;

数组最小容量 64

static final int MIN_TREEIFY_CAPACITY = 64;

#### 成员变量 ####

table 用来初始化（必须是二的n次幂）、

// 存储元素的数组 
    transient Node<K,V>[] table;

在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构，其中 table 就是 HashMap 中的数组，jdk8 之

[6744d7611631bab4c30b30336788dff6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/f1acdb3942914bcb9f8e9bacf3b7f2b3.png
[d5193de5678f40724b7a85c1f3a5485f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/05c19b41095b4bbfba62be9ab4d7942e.png