HashMap底层数据结构是数组 + 单向链表 + 红黑树
HashMap底层数据结构.png
一、相关概念
1、Hash冲突：就是在一个数组的位置上出现了一个链表，这就是所谓的hash冲突。
2、解决hash冲突，就是让链表的长度变短，或者干脆就是不产生链表，一个好的hash算法应该是让数据很好的散列到数组的各个位置，
即一个位置存一个数据就是最好的散列，下面说的链地址法，说的就是在hashmap里面冲突的时候，一个节点可以存多个数据。
3、桶(bucket)：数组中的每一个元素的位置就是一个桶。
4、HashMap的初始容量：16，并且 HashMap的底层数组长度总是2的n次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
HashMap的最大容量：2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
5、 HashMap的加载因子是：0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；
如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
6、将链表转为红黑树设置的链表长度的阈值：8
static final int TREEIFY_THRESHOLD = 8;
7、 从源码中可以看出，每次新建一个HashMap时，都会初始化一个table数组。table数组的元素为Node节点。
Node为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，正是由于Node才构成了table数组的项为链表。
8、创建一个Node类型的数组，transient 意思是不能序列化
transient Node<K,V>[] table;
二、计算key在数组中的位置
1、获取key的hash值
(h = key.hashCode()) ^ (h >>> 16)
● 通过hashCode方法获取到key的hash值，然后把hash值的低16位与高16位进行异或运算得到的值即为该key的hash值
● 原因：
因为后面要使用 (n - 1) & hash，所以通过hashCode方法获取的hash值不同也可能数组下标相同。为了降低运算结果值的相同概率，
使table数据分布均匀，减少碰撞
2、计算key在数组中的位置 【n是数组的容量，即长度】
①、对于HashMap的table数组而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，
太紧会导致查询速度慢，太松则浪费空间。
②、计算hash值后，怎么才能保证table数组中元素分布均与呢？我们会想到取模，但是由于取模的消耗较大，
HashMap是这样处理的：采用按位与运算，即 (n - 1) & hash，效率高，可以均匀分布table数据和充分利用空间。
③、原因：
● (n - 1) & hash 与 hash % n 是等值不等效 ， (n - 1) & hash 的效率高于 hash % n ，这是HashMap在速度上的一个优化。
● 按位取与，作用上相当于取模mod或者取余%。
★ 为什么 HashMap的底层数组长度总是2的n次方？
● 数组的默认长度是16，用二进制表示为： 10000
(n - 1) 即 (16 - 1) , 用二进制表示为：01111
因为数组长度总是2的n次方，所以如果扩容一次之后，数组的长度为32，用二进制表示为：100000
扩容一次后，(n - 1) 即 (32 - 1)，用二进制表示为： 011111
然后使用(n - 1) 与 key的 hash 进行 & 操作，结果是由key的hash值决定的(hash值是一个整型)
● 如果数组的长度不是2的n次方，假如数组的长度为15 ，则用二进制表示为：011111
则 (n - 1) 即 (15 - 1) , 用二进制表示为：011110
然后使用(n - 1) 与 key的 hash 进行 & 操作，因为数组长度不是2的n次幂，所以 (n - 1) 转换为二进制最后一位永远都是0 ，
& 的结果不能只由key的hash值决定的(hash值是一个整型)，所以空间减少，产生hash碰撞的概率就高
例如数组长度为9，hash值为3，计算其在数组上的位置为： 3 & (9 - 1) = 0 --> 0011 & 1000 = 0
数组长度为9，hash值为2，计算其在数组上的位置为：2 & (9 - 1) = 0 --> 0010 & 1000 = 0 在数组的相同位置上，发生碰撞；
例如数组长度为8，hash值为3，计算其在数组上的位置为：3 & (8 - 1) = 3 --> 0011 & 0111 = 0011
数组长度为8，hash值为2，计算其在数组上的位置为：2 & (8 - 1) = 2 --> 0010 & 0111 = 0010 不同位置上，不碰撞；
▲ 总结：数组的长度必须是2的n次幂，当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，
查询速度也较快。
三、HashMap的put方法执行过程可以通过下图来理解：
HashMap的put方法.png
①、调用put方法，首先判断数组table是否为null或数组的长度是否为0，如果是，就执行resize()进行扩容，转向②，如果不是，转向②；
②.根据键key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]位置的key是否和要添加的key相同(通过hashCode以及equals进行比较)，如果相同直接覆盖旧的value，添加新value，
并返回旧的value，否则转向⑥，，如果不同，转向④；
④.判断table[i] 是否 instanceof TreeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，转向⑥，否则转向⑤；
⑤、遍历table[i]位置的链表，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；
遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，数组长度加1，然后判断实际存在的键值对数量size是否超过了临界值threshold(数组容量 * 加载因子)，如果超过，进行扩容。
四、HashMap的resize方法执行过程：
★ resize()方法的作用：
初始化数组Node；
对数组进行扩容
①、获取原来数组的长度oldCap(oldCapacity)，进行判断：
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
②、如果数组长度oldCap > 0，判断数组长度oldCap是否 > 数组长度的最大值(2的30次方)，如果大于，则不进行扩容，返回原来的数组oldTab；
否则判断 oldCap << 1是否大于数组长度的最大值(2的30次方) 并且 oldCap是否 > 数组长度的最大值(2的30次方) ，
如果不大于，则进行扩容，即扩容后的数组长度为原来数组长度的2倍，临界值threshold也要左移1位，扩大到原来的2倍
③、如果数组长度oldCap <= 0，则对数组进行初始化操作，数组默认长度为16，临界值threshold(数组容量 * 加载因子)为12(16*0.75)；
newCap = DEFAULT_INITIAL_CAPACITY
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
④、创建新数组newTab，数组容量为扩容后的，即旧数组容量的2倍
⑤、判断旧数组是否使null，如果不是，则遍历旧数组，如果oldTab[i] ！= null，则把oldTab[i] = null 【把旧数组oldTab[i] 置空】
● 判断oldTab[i] 下面是不是null [即 e.next == null]，如果不存在，则重新计算oldTab[i] 在新数组中的位置
● 判断oldTab[i] 下面是一个红黑树，则把该红黑树进行split(分割)，然后重新计算在新数组中的位置
● 判断oldTab[i] 下面是一个链表(该链表的长度不会超过8)，则进行循环遍历，新数组中元素的位置只可能在两个地方，
一个是原下标的位置，另一个是下标为 [原下标 + 原容量] 的位置
● 如果 (e.hash & oldCap) == 0，则新数组中元素的位置在原下标的位置
● 如果 (e.hash & oldCap) != 0，则新数组中元素的位置在下标为 [原下标 + 原容量] 的位置
⑥、返回新数组newTab
