Java基础-HashMap

1.结构（JDK1.7）

JDK1.8引入了红黑树，当链表的长度大于8，且数组的大少大于等于64时，链表会转换为红黑树。 当红黑树的结点个数小于6时，会转换为链表 HashMap底层主要代码：

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.75threshold：扩容的阈值，决定了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.数据插入原理

插入流程：

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

图片来源：blog.csdn.net/zhengwangzw