HashMap的扩容机制

 1 final Node[] resize() {
 2     Node[] oldTab = table;
 3     int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4     int oldThr = threshold;
 5     int newCap, newThr = 0;
 6     if (oldCap > 0) {
 7         if (oldCap >= MAXIMUM_CAPACITY) {
 8             threshold = Integer.MAX_VALUE;
 9             return oldTab;
10         }
11         else if ((newCap = oldCap <<1) 12                  oldCap >= DEFAULT_INITIAL_CAPACITY)
13             newThr = oldThr <<1; // double threshold
14     }
15     else if (oldThr > 0) // initial capacity was placed in threshold
16         newCap = oldThr;
17     else {               // zero initial threshold signifies using defaults
18         newCap = DEFAULT_INITIAL_CAPACITY;
19         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20     }
21     if (newThr == 0) {
22         float ft = (float)newCap * loadFactor;
23         newThr = (newCap float)MAXIMUM_CAPACITY ?
24                   (int)ft : Integer.MAX_VALUE);
25     }
26     threshold = newThr;
27     @SuppressWarnings({"rawtypes","unchecked"})
28         Node[] newTab = (Node[])new Node[newCap];
29     table = newTab;
30     //移动数据
31     if (oldTab != null) {
32         for (int j = 0; j j) {
33             Node e;
34             if ((e = oldTab[j]) != null) {
35                 oldTab[j] = null;
36                 if (e.next == null)
37                     newTab[e.hash & (newCap - 1)] = e;
38                 else if (e instanceof TreeNode)
39                     ((TreeNode)e).split(this, newTab, j, oldCap);
40                 else { // preserve order
41                     Node loHead = null, loTail = null;
42                     Node hiHead = null, hiTail = null;
43                     Node next;
44                     do {
45                         next = e.next;
46                         //把元素的hash值与旧的容量做&运算，便可得出元素的hash值
47                         //新增的参与运算的那一bit是1还是0
48                         //hash&(n-1) 与 hash & n  的区别：
49                         //加入n为16，则n-1为：1111 ，n为：10000
50                         //n比n-1高了一bit，且因为n为2的n次幂，
51                         //所以，hash&n 可以得出扩容后元素hash值多参与运算的那一bit是0还是1
52                         //新增参与运算的bit是0，则位置不变
53                         if ((e.hash & oldCap) == 0) {
54                             if (loTail == null)
55                                 loHead = e;
56                             else
57                                 loTail.next = e;
58                             loTail = e;
59                         }
60                         //新增参与运算的bit是1，位置变为： 原索引+原数组容量
61                         else {
62                             if (hiTail == null)
63                                 hiHead = e;
64                             else
65                                 hiTail.next = e;
66                             hiTail = e;
67                         }
68                     } while ((e = next) != null);
69                     if (loTail != null) {
70                         loTail.next = null;
71                         //位置不变
72                         newTab[j] = loHead;
73                     }
74                     if (hiTail != null) {
75                         hiTail.next = null;
76                         //位置变为： 原索引+原数组容量
77                         newTab[j + oldCap] = hiHead;
78                     }
79                 }
80             }
81         }
82     }
83     return newTab;
84 }