HashMap实现原理（JDK1.8）
1 /**
2 * Initializes or doubles table size. If null, allocates in
3 * accord with initial capacity target held in field threshold.
4 * Otherwise, because we are using power-of-two expansion, the
5 * elements from each bin must either stay at same index, or move
6 * with a power of two offset in the new table.
7 *
8 * @return the table
9 */
10 final Node[] resize() {
11 Node[] oldTab = table;
12 int oldCap = (oldTab == null) ? 0 : oldTab.length;
13 int oldThr = threshold;
14 int newCap, newThr = 0;
15
16 /*如果旧表的长度不是空*/
17 if (oldCap > 0) {
18 if (oldCap >= MAXIMUM_CAPACITY) {
19 threshold = Integer.MAX_VALUE;
20 return oldTab;
21 }
22 /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
23 else if ((newCap = oldCap << 1) = DEFAULT_INITIAL_CAPACITY)
25 /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
26 newThr = oldThr < 0) // initial capacity was placed in threshold
30 newCap = oldThr;
31 else { // zero initial threshold signifies using defaults
32 newCap = DEFAULT_INITIAL_CAPACITY;
33 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
34 }
35
36
37
38 if (newThr == 0) {
39 float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
40 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
41 (int)ft : Integer.MAX_VALUE);
42 }
43 threshold = newThr;
44 @SuppressWarnings({"rawtypes","unchecked"})
45 /*下面开始构造新表，初始化表中的数据*/
46 Node[] newTab = (Node[])new Node[newCap];
47 table = newTab;//把新表赋值给table
48 if (oldTab != null) {//原表不是空要把原表中数据移动到新表中
49 /*遍历原来的旧表*/
50 for (int j = 0; j < oldCap; ++j) {
51 Node e;
52 if ((e = oldTab[j]) != null) {
53 oldTab[j] = null;
54 if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
55 newTab[e.hash & (newCap - 1)] = e;
56 else if (e instanceof TreeNode)
57 ((TreeNode)e).split(this, newTab, j, oldCap);
58 /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/
59 else { // preserve order保证顺序
60 ////新计算在新表的位置，并进行搬运
61 Node loHead = null, loTail = null;
62 Node hiHead = null, hiTail = null;
63 Node next;
64
65 do {
66 next = e.next;//记录下一个结点
67 //新表是旧表的两倍容量，实例上就把单链表拆分为两队，
68 //e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
69 if ((e.hash & oldCap) == 0) {
70 if (loTail == null)
71 loHead = e;
72 else
73 loTail.next = e;
74 loTail = e;
75 }
76 else {
77 if (hiTail == null)
78 hiHead = e;
79 else
80 hiTail.next = e;
81 hiTail = e;
82 }
83 } while ((e = next) != null);
84
85 if (loTail != null) {//lo队不为null，放在新表原位置
86 loTail.next = null;
87 newTab[j] = loHead;
88 }
89 if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置
90 hiTail.next = null;
91 newTab[j + oldCap] = hiHead;
92 }
93 }
94 }
95 }
96 }
97 return newTab;
98 }
HashMap扩容可以分为三种情况：
第一种：使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
第二种：指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） * DEFAULT_LOAD_FACTOR。
第三种：HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。
这边也可以引申到一个问题HashMap是先插入还是先扩容：HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。
将原数组元素平移至新数组：
如果旧数组不为空，当我们在扩容时就需要将旧数组的数组迁移到新数组，数据迁移需要遍历旧数组，将旧数组每一个数组下标index的数据移动到新数组中。如果遍历数组时发现当前位置存放着Node链表，这个时候需要对Node结点的Hash值与新数组长度进行&运算。如果计算出来的值为0，将旧数组当前位置的Node链表赋值到新数组相同位置，即newTab[j] = loHead。如果计算出来的值不为0，此时将当前位置的Node链表赋值给新数组当前位置加上旧数组长度的位置，即newTab[j + oldCap] = hiHead。
如果想要理解这个过程，需要首先明白JDK1.8中HashMap如何计算数组下标。
int index = node.hash&(table.length-1);
&运算能够保证计算出来的值小于等于其中任何一个值，因此计算出来的数组下标index小于等于table.length-1。
可是在数组两倍扩容后，数组的长度发生了变化，同时我们也必须要严格遵守数组下标index的算法，否则在get时无法获取到对应Node结点。因此将旧数组中的数据迁移到新数组后，需要按照新数组长度重新计算数组下标。如果还是通过&运算计算数组下标，我们就需要遍历数组中所有的结点，并计算出结点的Hash值，并将Hash值与数组的长度减1进行&运算得出数组下标。而HashMap的实现者明显找到了更便捷的算法。而这种算法分为两种情况。
注：注意Node结点Hash值二进制表示的标红位数变化。
情况一：Hash值与旧数组长度的&运算不为0
node.hash & oldTable.length != 0;
我们假设Node结点的Hash值的二进制是1000010101，旧数组长度为16，二进制即10000。此时计算出来的index为5。
Hash ：1000010101
length-1 ：0000001111
——————————
index : 0000000101
当我们对数组进行扩容，数组的长度变成了32，Node结点的Hash值依然为1000010101。此时计算出来的index为21。
Hash ：1000010101
length-1 ：0000011111
——————————
index : 0000010101
结点平移后，此时计算出来的存放结点的新数组下标为旧数组下标加上旧数组的长度，即newIndex = oldIndex+oldLength；
情况二：Hash值与旧数组长度的&运算为0
node.hash & oldTable.length == 0;
我们假设Node结点的Hash值的二进制是1000000101，旧数组长度为16，二进制即10000。此时计算出来的index为5。
Hash ：1000010101
length-1 ：0000001111
——————————
index : 0000000101
当我们对数组进行扩容，数组的长度变成了32，Node几点的Hash值依然为1000000101。此时计算出来的index仍为5。
Hash ：1000000101
length-1 ：0000011111
——————————
index : 0000000101
结点平移后，此时计算存放结点的新数组下标与旧数组下标相等，即newIndex = oldIndex。
About The Author
