Java基础-HashMap

野性酷女 2023-02-22 10:49 10阅读 0赞

## 1.结构 ##

JDK1.8引入了红黑树，**当链表的长度大于8，且数组的大少大于等于64时，链表会转换为红黑树**。  
当红黑树的结点个数小于6时，会转换为链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70]  
HashMap底层主要代码：

成员变量：

// Hash表默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    // 最大Hash表容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 链表转红黑树阈值
    static final int TREEIFY_THRESHOLD = 8;
    
    // 红黑树转链表阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 链表转红黑树时hash表最小容量阈值，达不到优先扩容
    static final int MIN_TREEIFY_CAPACITY = 64;

transient Entry[] table;

从代码中可以看到一个hashmap的主干就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组。

static class Entry<K,V> implements Map.Entry<K,V> {   
            final K key;  
            V value;  
            final int hash;  
            Entry<K,V> next;  
    ..........  
    }

Entry就是数组中的元素，它持有一个指向下一个元素的引用，这就构成了链表。  
往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的

## 2.扩容机制 ##

##### 2.1变量： #####

*  Node<K,V>：链表节点，包含了key、value、hash、next指针四个元素
 *  table：Node<K,V>类型的数组，里面的元素是链表，用于存放HashMap元素的实体，即容量，默认16。
 *  size：记录了放入HashMap的元素个数
 *  **loadFactor：负载因子**，默认是0.75
 *  **threshold：扩容的阈值，决定了HashMap何时扩容，以及扩容后的大小，一般等于，等于 table \* loadFactor**，默认12。当元素数量超过阈值时便会触发扩容。

##### 2.2扩容时间： #####

HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素之前，HashMap并不会去初始化或者扩容table。  
当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化，当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容

##### 2.3JDK7扩容机制： #####

*  空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。
 *  有参构造函数：根据参数确定容量、负载因子、阈值等。
 *  第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。
 *  如果不是第一次扩容，则 新容量 = 旧容量 \* 2；新阈值 = 新容量 \* 负载因子

##### 2.4JDK8扩容机制： #####

*  空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，**默认长度为16**
 *  有参构造函数：用于指定容量，会根据指定的正整数找到不小于指定容量的2的幂数（**初始化的大少 > 传入参数的 2 的整数次方**），将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 阈值 = 容量 \* 负载因子。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容）
 *  如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）
 *  首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容
 *  不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容

简单来说：  
扩容，即是创建一个新的Entry空数组，长度是原数组的2倍。然后遍历原Entry数组，把所有的Entry重新Hash到新数组

重新哈希的原因：  
Hash的公式：index = HashCode（Key） & （Length - 1）  
因为数组的长度发生了改变

## 3.数据插入原理 ##

插入流程：

1.  判断数组是否为空，为空则进行初始化
2.  不为空，计算 k 的 hash 值，通过 (n - 1) & hash 计算应当存放在数组中的下标 index
3.  判断计算出的 index 处是否已存在数据，没有存在数据，则直接插入该数据。如果已经存在数据，则说明发生了哈希冲突，继续进行下一步
4.  判断要插入的数据的 Key 和已经存在的数据的 Key 是否相等，如果相等，则直接把要插入的数据的 value 覆盖已存在的数据的 value 即可
5.  如果不相等，则需要判断当前的数据结点类型是链表类型还是树型结点。如果是树型结点，则把该数据插入红黑树的叶子结点即可
6.  如果该结点是链表类型，则创建一个普通 Node 加入链表中。插入完成后，判断链表长度是否大于8，且数组长度大于64，满足的话则转换成红黑树
7.  插入完成后，判断当前结点树是否大于阈值，大于的话则开始扩容，扩容为原数组的2倍

图片来源：blog.csdn.net/zhengwangzw  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]

**图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200703000940899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200918114706194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210524171141790.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg==,size_16,color_FFFFFF,t_70