【Java集合二】HashMap 详解
一、简介
1.1 概述
JDK1.8之前：HashMap使用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度>8（新插入的Node是链表第9个）且数组长度>=64时，将链表转换为红黑树，这样大大减少了查找时间。
下图中代表jdk1.8之前的HashMap结构，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。jdk1.8之前的hashmap都采用下图的结构，都是基于一个数组和多个单链表，hash值冲突的时候，就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时，将会花费O（n）的查找时间，会有很大的性能损失。
到了jdk1.8，HashMap的数据结构为 数组+链表+红黑树，当链表长度>=8（新插入的Node是链表第8个）且数组长度>=64时，将链表转换为红黑树，这样大大减少了查找时间。如下图所示：
1.2 HashMap涉及到的数据结构
1.2.1 链表
Node是HashMap的一个内部类，实现了Map.Entry接口，本质上是一个映射（键值对）。上图中每一个黑圆点就是一个Node对象。来看具体代码：
可以看到，node中包含一个 next 变量，这个就是链表的关键点，hash 结果相同的元素就是通过这个 next 进行关联的。
1.2.2 红黑树
1.2.2.1 红黑树概述
红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。红黑树的时间复杂度为O(lgn)。
- (1) 节点都有颜色
- (2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
- 每一个节点不是红色的就是黑色的
- 根总是黑色的
- 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）
- 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
- 如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
1.2.2.2 HashMap中的红黑树
红黑树节点 TreeNode 比链表节点 Node 多了四个变量，parent父节点、left左节点、right右节点、prev上一个同级节点
1.2.3 位桶
HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。
二、源码解析
2.1 java7 HashMap
HashMap里面是一个数组，然后数组中每个元素是一个单向链表。
上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。
capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
loadFactor：负载因子，默认为 0.75。
threshold：扩容的阈值，等于 capacity * loadFactor。
2.1.1 put方法介绍
2.1.1.1. 数组初始化 inflateTable
在第一个元素插入 HashMap 的时候做一次数组的初始化，就是先确定初始的数组大小，并计算数组扩容的阈值。
这里有一个将数组大小保持为 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相应的要求，只不过实现的代码稍微有些不同，后面再看到的时候就知道了。
2.1.1.2 计算数组具体位置 indexFor
取 hash 值的低 n 位。如在数组长度为 32 的时候，其实取的就是 key 的 hash 值的低 5 位，作为它在数组中的下标位置。
2.1.1.3 添加节点到链表中 addEntry
找到数组下标后，会先进行 key 判重，如果没有重复，就准备将新值放入到链表的表头。
这个方法的主要逻辑就是先判断是否需要扩容，需要的话先扩容，然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头。
HashMap的hash碰撞解决方案——拉链法:
jdk 中的 Hashmap 采用的是拉链法去解决整个问题的，也就是说当相同的 hash 值找到同样一个位置的时候，采用链表存储。
如上图，put 过程中确定 key 是否重复要判断 hash 值和 key 是否都相同，所以不同 key 产生hash碰撞时，最终会进入 addEntry 方法，在该方法中把键值对添加到链表头部也就是 table[i] 处，此方法被称为拉链法。
头插法：在往 HashMap 里面 put 元素时，此时新增在链表上元素的位置为链表头部，也就是数组桶位上的那个位置，故名头插法。
直到 addEntry(hash, key, value, i) 才是头插法的实现开始：
大家注意这个参数 bucketIndex，它是之前用 key 的哈希值做过位运算之后再去找数组运算得到的下标。如果要将 key-value 这个键值对放入 hashmap 的话，就会放到数组的这个位置或者这个位置的链表上。
Entry e = table[bucketIndex] 这一句则取到数组上这个下标的元素，然后作为new Entry<>(hash, key, value, e)的参数 e ，这个 e 就是它的下一个节点。
2.1.1.4 数组扩容 resize
前面我们看到，在插入新值的时候，如果当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素，那么就会触发扩容，扩容后，数组大小为原来的 2 倍。
扩容就是用一个新的大数组替换原来的小数组，并将原来数组中的值迁移到新的数组中。
由于是双倍扩容，迁移过程中，会将原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16，那么扩容后，原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置。
2.1.1.5 数组扩容中的数组元素迁移 transfer()
- foreach 循环遍历旧数组 table，在 foreach 循环内部通过 while 循环遍历该桶位的链表。
- 假设现在刚刚插入到新数组上，因为是对象数组且数组都是要默认有初始值的，所以这个新数组 newTable 的初始值都是null。 e1.next = newTable[i] 这行代码也就相当于 e1.next = null 。然后再 newTable[i] = e1 ；也就是说，这个时候这个数组的这个下标位置的值设置成这个e1了。
- 假设这个时候继续上面的循环，又取第二个数据e2的时候，如果恰好e2的下标和刚刚上面的e1下标相同，那么这个时候有链表要产生了。假设上面第一次存的叫e1，那么现在 e2.next = newTable[i] 这行代码也就相当于 e2.next = e1 ；然后再跑 newTable[i] = e 这行代码把 e2 赋值在数组下标为i的位置。注意：现在的 e2.next 指向的是刚刚的e1，e1的next是null。
2.1.2 并发情况下会产生的问题
- java1.7 HashMap多线程 put 后可能导致 get 死循环，具体表现为CPU使用率100% ：resize() ---> transfer()方法再散列调整table大小的过程 进行了一次倒序处理， 在这里并发情况下可能会出现环形链。
- 多线程put的时候可能导致元素丢失 ：在多线程下put操作时，执行 addEntry(hash, key, value, i) ，如果有产生哈希碰撞，导致两个线程得到同样的 bucketIndex 去存储，就可能会出现覆盖丢失的情况。
2.1.2.1 多线程下扩容反转导致环形链情况的具体解析
- 先是执行newTable[i] = e ;
- 然后是e = next , 导致了e指向了key(7);
- 而下一次循环的next = e.next 导致next指向了key(3)
总结：
线程A先执行，执行完 Entry next = e.next; 这行代码后挂起，然后线程B完整的执行完整个扩容流程，接着线程A唤醒，继续之前的往下执行，当while循环执行3次后会形成环形链表。
2.1.3 get方法介绍
- 根据 key 计算 hash 值：(h = key.hashCode()) ^ (h >>> 16)
- 找到相应的数组下标：hash & (length - 1)。
- 遍历该数组位置处的链表，直到找到相等(==或equals)的 key。
2.2 java8 HashMap
Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性。
不过，Java8 中的 Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树。
注意：当链表长度>8（新插入的Node是链表第9个）且数组长度>=64时，才会将链表转换为红黑树。
当 binCount=0 ，put的第2个元素（p.next=newNode(...)），binCount 1 对应 put 的第3个元素，以此类推，当 binCount=7 时此时 put 的是第9个元素，而上面的已经说了binCount >=7时调用treeifyBin方法，所以链表长度是要超过8。
2.2.1 类的属性
2.2.2 类的构造方法
说明：tableSizeFor(initialCapacity) 返回大于 initialCapacity 的最小的二次幂数值。int n = cap - 1是为了防止 cap 已经是2的幂。
2.2.3 hash算法
2.2.3.1 源码分析
在JDK 1.8中，hash方法如下：
（1）首先获取对象的 hashCode 值，然后将 hashCode 值右移16位，然后将右移后的值与原来的 hashCode 做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。
（2）在 putVal() 方法的源码中，我们通过 (n-1)&hash 获取该对象的键在 Hashmap 中的位置。（其中 hash 的值就是（1）中获得的值）其中 n 表示的是 HashMap 桶数组的长度，由上文可知该长度为2的n次方，这样 (n-1)&hash 就等价于 hash%n 。因为&运算的效率高于%运算。
n：hash槽数组大小 i：Node在数组中的索引值
上述关键代码： i = (n - 1) & hash
tab 即是 table ，n 是 map 集合的容量大小，hash 是上面方法的返回值。虽然容量的2进制高位一开始都是0，但是 key.hashCode() 的2进制高位通常是有值的，因此先在hash() 方法中将 key.hashCode() 右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。
^ ：按位运算符，异或
0 ^ 1 得 1
1 ^ 1 得 0
0 ^ 0 得 0
1 ^ 0 得 1
2.2.3.2 扩容位置变化推演
在 jdk1.8 中，resize() 方法是在 Hashmap 中的键值对数大于阀值时或者初始化时，就调用 resize() 方法进行扩容。
下面我们推演一下，当扩容时，原 Node 节点在新老数组中的位置变化：
final Node<K,V>[] resize() {
//......
//遍历旧数组，数据迁移到新数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//hash(key) 的值高位为0的
Node<K,V> loHead = null, loTail = null;
//hash(key) 的值高位为1的
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //判断 hash(key) 的值高位是否为0
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//hash(key) 的值高位为0的放入原位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//hash(key) 的值高位为1的放入 原索引+扩容的长度 位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
//......
}- 还在原来的数组索引上
- 原索引+扩容的长度
2.2.3.3 HashMap 的容量为什么建议是 2的幂次方？
hash 算法的目的是为了让 hash 值均匀的分布在桶中（数组），那么，如何做到呢？试想一下，如果不使用 2 的幂次方作为数组的长度会怎么样？
假设我们的数组长度是10，还是上面的公式：(n - 1) & hash
1001 & 101010100101001001000 结果：1000 = 8
1001 & 101000101101001001001 结果：1001 = 9
1001 & 101010101101101001010 结果：1000 = 8
1001 & 101100100111001101100 结果：1000 = 8看到结果我们就明白了，这种散列结果，会导致这些不同的 key 值全部进入到相同的插槽中，形成链表，性能急剧下降。
所以说，我们一定要保证 & 之前的二进制位全为 1，才能最大限度的利用 hash 值，并更好的散列，只有全是1 ，才能有更多的散列结果。如果是 1010，有的散列结果是永远都不会出现的，比如 0111，0101，1111，1110…，只要 & 之前的数有 0， 对应的 1 肯定就不会出现（因为只有都是1才会为1）。大大限制了散列的范围。
2.2.4 重要方法分析
2.2.4.1 putVal 方法
和 Java7 稍微有点不一样的地方就是，Java7 是先扩容后插入新值的，Java8 先插值再扩容。
首先说明，HashMap 并没有直接提供 putVal() 接口给用户调用，而是提供的put方法，而 put() 方法就是通过 putVal() 来插入元素的。
putVal() 方法执行过程可以通过下图来理解：
具体源码如下：
- 1. 根据 key 计算得到 key 的 hash 值： key.hash = (h = k.hashCode()) ^ (h >>> 16)；
- 2. 根据 key.hash 计算得到桶数组的索引 index = key.hash & (table.length - 1) ，这样就找到该key的存放位置了：
- ① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；
- ② 如果该位置有数据是一个红黑树，那么执行红黑树相应的插入 / 更新操作；
- ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点 (注意这里判断的依据是key.hash是否一样)：
- 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，插入后判断链表长度是否大于8，大于8的话（且数组的长度大于64）把链表转换为红黑树，跳出循环，继续判断是否需要扩容，最后返回null；
- 如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。
【注意】：HashMap的put会返回key的上一次保存的数据。
【注意】：底层通过一个 modCount 值记录修改的次数，对 HashMap 的修改操作都会增加这个值。迭代器在初始过程中会将这个值赋给 exceptedModCount ，在迭代的过程中，如果发现 modCount 和 exceptedModCount 的值不一致，代表有其他线程修改了Map，就会立刻抛出异常。
2.2.4.2 getNode方法
说明：HashMap 同样并没有直接提供 getNode() 方法给用户调用，而是提供的 get() 方法，而 get() 方法就是通过 getNode() 来取得元素的。
- 一、计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)。
- 二、判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步。
- 三、判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据；如果不是，走第四步。
- 四、遍历链表，直到找到相等(==或equals)的 key。
2.2.4.3 resize 方法
①. 在jdk1.8中，resize() 方法是在 HashMap 中的键值对大于阀值时或者初始化时，就调用 resize() 方法进行扩容；
②. 每次扩展的时候，都是扩展2倍；
③. 扩展后 Node 对象的位置要么在原位置，要么移动到 原偏移+扩容长度 的位置。
resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。
- Node loHead = null, loTail = null; 对应 key.hash 高位为0的情况，这条链表在扩容后会放回原位；
- Node hiHead = null, hiTail = null; 对应 key.hash 高位为1的情况，这条链表在扩容后会放在 原位置+扩容长度 的位置。
2.2.5 HashMap 链表转换成红黑树
当数组中某个位置的节点达到8个时，会触发 treeifyBin() 方法将链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点后，链表结构就不存在了。当数组中某个位置的节点在移除后达到6个时，并且该索引位置的节点为红黑树节点，会触发 untreeify() 将红黑树节点转化成链表节点。
HashMap 在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion ）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、改变节点颜色（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。
当链表长过长时会转换成红黑树，那能不能使用AVL树替代呢？
AVL树是完全平衡二叉树，要求每个结点的左右子树的高度之差的绝对值最多为1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，虽然会导致红黑树的查询会比AVL稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。