本篇隨筆主要描述的是我閱讀 HashMap 源碼期間的對于 HashMap 的一些實現(xiàn)上的個人理解，用于個人備忘诱担，有不對的地方鲫售，請指出～

接下來會從以下幾個方面介紹 HashMap 源碼相關(guān)知識：

1、HashMap 存儲結(jié)構(gòu)

2该肴、HashMap 各常量情竹、成員變量作用

3、HashMap 幾種構(gòu)造方法

4、HashMap put 及其相關(guān)方法

5秦效、HashMap get 及其相關(guān)方法

6雏蛮、HashMap remove 及其相關(guān)方法（暫未理解透徹）

7、HashMap 擴容方法　resize()

介紹方法時會包含方法實現(xiàn)相關(guān)細(xì)節(jié)阱州。

先來看一下 HashMap 的繼承圖：

image

HashMap 根據(jù)鍵的 hashCode 值存儲數(shù)據(jù)挑秉，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap 最多只允許一條記錄的鍵為 null 脾拆，允許多條記錄的值為 null 。HashMap 非線程安全姻灶，即任一時刻可以有多個線程同時寫 HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致诈茧。如果需要滿足線程安全产喉，可以用 Collections的synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用ConcurrentHashMap 敢会。

一曾沈、HashMap 存儲結(jié)構(gòu)

HashMap是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的，如下圖所示：

源碼中具體實現(xiàn)如下：

1 　// Node<K,V> 類用來實現(xiàn)數(shù)組及鏈表的數(shù)據(jù)結(jié)構(gòu)
2 　 static class Node<K,V> implements Map.Entry<K,V> { 
3         final int hash; //保存節(jié)點的 hash　值 
4         final K key; //保存節(jié)點的　key　值
5         V value;　//保存節(jié)點的　value 值
6         Node<K,V> next;　//指向鏈表結(jié)構(gòu)下的當(dāng)前節(jié)點的　next 節(jié)點鸥昏，紅黑樹　TreeNode　節(jié)點中也有用
7 
8         Node(int hash, K key, V value, Node<K,V> next) { 
9             this.hash = hash;
10             this.key = key; 11             this.value = value; 
12             this.next = next; 
13 } 
14 
15         public final K getKey()        { } 
16         public final V getValue()      {  } 
17         public final String toString() { } 
18 
19         public final int hashCode() { 
20         }
21 
22         public final V setValue(V newValue) {
23         }
24 
25         public final boolean equals(Object o) { 
26         } 
27         } 
28     
29     public class LinkedHashMap<K,V> { 
30           static class Entry<K,V> extends HashMap.Node<K,V> { 
31                 Entry<K,V> before, after; 
32                 Entry(int hash, K key, V value, Node<K,V> next) {
33                     super(hash, key, value, next); 
34                 } 
35           } 
36     } 
37     
38 　// TreeNode<K,V> 繼承 LinkedHashMap.Entry<K,V>塞俱，用來實現(xiàn)紅黑樹相關(guān)的存儲結(jié)構(gòu)
39     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
40         TreeNode<K,V> parent;  // 存儲當(dāng)前節(jié)點的父節(jié)點
41         TreeNode<K,V> left;　//存儲當(dāng)前節(jié)點的左孩子 
42         TreeNode<K,V> right;　//存儲當(dāng)前節(jié)點的右孩子 
43         TreeNode<K,V> prev;    // 存儲當(dāng)前節(jié)點的前一個節(jié)點
44         boolean red;　// 存儲當(dāng)前節(jié)點的顏色（紅、黑） 
45         TreeNode(int hash, K key, V val, Node<K,V> next) { 
46             super(hash, key, val, next); 
47         } 
48        
49         final TreeNode<K,V> root() { 
50         }
51       
52         static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { 
53         }
 
54       
55         final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
56         }
57      
58         final void treeify(Node<K,V>[] tab) { 
59         } 
60      
61         final Node<K,V> untreeify(HashMap<K,V> map) { 
62         }
63        
64         final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, 
65                                        int h, K k, V v) { 
66         } 
67         
68         final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, 
69                                boolean movable) { 
70         } 
71 
72         final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 73 } 74 
75         /* ------------------------------------------------------------ */
76         // Red-black tree methods, all adapted from CLR 
77         // 紅黑樹相關(guān)操作
78         static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, 
79                                               TreeNode<K,V> p) { 
80         } 
81 
82         static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, 
83                                                TreeNode<K,V> p) { 
84         } 
85 
86         static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 
87                                                     TreeNode<K,V> x) { 
88         } 
89 
90         static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, 
91                                                    TreeNode<K,V> x) { 
92         } 
93 
94         static <K,V> boolean checkInvariants(TreeNode<K,V> t) { 
95         }
96 
97     }

二吏垮、HashMap 各常量障涯、成員變量作用

 1　   //創(chuàng)建 HashMap 時未指定初始容量情況下的默認(rèn)容量 
 2     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
 3 
 4 　//HashMap 的最大容量
 5     static final int MAXIMUM_CAPACITY = 1 << 30;
 6 
 7     //HashMap 默認(rèn)的裝載因子,當(dāng) HashMap 中元素數(shù)量超過 容量*裝載因子 時，進(jìn)行　resize()　操作
 8     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9 
10     //用來確定何時將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹
11     static final int TREEIFY_THRESHOLD = 8; 12 
13     // 用來確定何時將解決 hash 沖突的紅黑樹轉(zhuǎn)變?yōu)殒湵?14     static final int UNTREEIFY_THRESHOLD = 6; 15  
16     /* 當(dāng)需要將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹時惫皱，需要判斷下此時數(shù)組容量像樊，若是由于數(shù)組容量太杏容骸（小于　MIN_TREEIFY_CAPACITY÷梅蟆）導(dǎo)致的 hash 沖突太多，則不進(jìn)行鏈表轉(zhuǎn)變?yōu)榧t黑樹操作颤霎，轉(zhuǎn)為利用　resize() 函數(shù)對　hashMap 擴容*/
17     static final int MIN_TREEIFY_CAPACITY = 64;

 1 //保存Node<K,V>節(jié)點的數(shù)組
 2  transient Node<K,V>[] table;
 3 
 4 //由　hashMap 中 Node<K,V>　節(jié)點構(gòu)成的 set
 5 transient Set<Map.Entry<K,V>> entrySet; 6 
 7 //記錄 hashMap 當(dāng)前存儲的元素的數(shù)量
 8 transient int size; 9 
10 //記錄　hashMap 發(fā)生結(jié)構(gòu)性變化的次數(shù)（注意　value 的覆蓋不屬于結(jié)構(gòu)性變化）
11 transient int modCount; 12 
13 //threshold的值應(yīng)等于 table.length * loadFactor, size 超過這個值時進(jìn)行　resize()擴容
14 int threshold; 15 
16 //記錄 hashMap 裝載因子
17 final float loadFactor;

三媳谁、HashMap 幾種構(gòu)造方法

 1 //構(gòu)造方法１，指定初始容量及裝載因子
 2 public HashMap(int initialCapacity, float loadFactor) { 
 3        if (initialCapacity < 0)
 4             throw new IllegalArgumentException("Illegal initial capacity: " +
 5                                                initialCapacity);
 6        if (initialCapacity > MAXIMUM_CAPACITY) 
7             initialCapacity = MAXIMUM_CAPACITY; 
8         if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
9             throw new IllegalArgumentException("Illegal load factor: " +
10         loadFactor); 
11         this.loadFactor = loadFactor; 
12     　/* tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的2的冪友酱，若指定初始容量為９晴音，則實際 hashMap 容量為16*/
13     　//注意此種方法創(chuàng)建的 hashMap 初始容量的值存在　threshold 中
14         this.threshold = tableSizeFor(initialCapacity); 
15 } 
16         //tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的2的冪
17         static final int tableSizeFor(int cap) { 
18                 int n = cap - 1; 
19                 n |= n >>> 1;// >>> 代表無符號右移 
20                 n |= n >>> 2; 
21                 n |= n >>> 4; 
22                 n |= n >>> 8; 
23                 n |= n >>> 16; 
24                 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
25         } 
26       //構(gòu)造方法２，僅指定初始容量缔杉，裝載因子的值采用默認(rèn)的　0.75
27         public HashMap(int initialCapacity) { 
28                 this(initialCapacity, DEFAULT_LOAD_FACTOR); 
29         } 
30         //構(gòu)造方法３锤躁，所有參數(shù)均采用默認(rèn)值
31         public HashMap() { 
32                 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
33         }

四、HashMap put 及其相關(guān)方法

這部分我覺得是　hashMap 中比較重要的代碼或详，介紹如下：

 1 　//指定節(jié)點 key,value系羞，向 hashMap 中插入節(jié)點
 2 　public V put(K key, V value) { 
 3     　//注意待插入節(jié)點　hash 值的計算郭计，調(diào)用了　hash(key) 函數(shù)
 4 　　//實際調(diào)用 putVal（）進(jìn)行節(jié)點的插入
 5         return putVal(hash(key), key, value, false, true);
 6     }
 7 　static final int hash(Object key) { 
8         int h; 
9 　　/*key 的 hash　值的計算是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度椒振、功效昭伸、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時候澎迎，也能保證考慮到高低Bit都參與到Hash的計算中庐杨，同時不會有太大的開銷*/
10         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
11     } 
12 
13 　public void putAll(Map<? extends K, ? extends V> m) { 
14         putMapEntries(m, true); 
15 } 
16 　
17 　/*把Map<? extends K, ? extends V> m 中的元素插入到　hashMap 中,若 evict 為 false,代表是在創(chuàng)建 hashMap 時調(diào)用了這個函數(shù)，例如利用上述構(gòu)造函數(shù)３創(chuàng)建 hashMap;若 evict　為true,代表是在創(chuàng)建　hashMap 后才調(diào)用這個函數(shù)夹供，例如上述的　putAll 函數(shù)灵份。*/
18 
19 　final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
20         int s = m.size(); 
21         if (s > 0) { 
22             /*如果是在創(chuàng)建 hashMap 時調(diào)用的這個函數(shù)則 table 一定為空*/
23             if (table == null) { 
24 　　　　  //根據(jù)待插入的map 的 size 計算要創(chuàng)建的　hashMap 的容量。
25                 float ft = ((float)s / loadFactor) + 1.0F; 
26                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
27                          (int)ft : MAXIMUM_CAPACITY); 
28 　　　　  //把要創(chuàng)建的　hashMap 的容量存在　threshold　中
29                 if (t > threshold) 
30                     threshold = tableSizeFor(t); 
31 } 
32 　　　 //判斷待插入的　map 的 size,若　size 大于　threshold罩引，則先進(jìn)行　resize()
33             else if (s > threshold) 
34 resize(); 
35             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
36                 K key = e.getKey(); 
37                 V value = e.getValue(); 
38                 //實際也是調(diào)用　putVal　函數(shù)進(jìn)行元素的插入
39                 putVal(hash(key), key, value, false, evict);
 40 } 
41 } 
42 } 
43 　
44     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
45                    boolean evict) { 
46         Node<K,V>[] tab; Node<K,V> p; int n, i; 
47         if ((tab = table) == null || (n = tab.length) == 0) 
48             n = (tab = resize()).length; 
49 　　 /*根據(jù) hash 值確定節(jié)點在數(shù)組中的插入位置各吨，若此位置沒有元素則進(jìn)行插入，注意確定插入位置所用的計算方法為　(n - 1) & hash,由于　n 一定是２的冪次袁铐，這個操作相當(dāng)于 
50 hash % n */
51         if ((p = tab[i = (n - 1) & hash]) == null) 
52             tab[i] = newNode(hash, key, value, null); 
53         else {//說明待插入位置存在元素
54             Node<K,V> e; K k; 
55 　　　 　　　　//比較原來元素與待插入元素的　hash 值和　key 值
56             if (p.hash == hash &&
57                 ((k = p.key) == key || (key != null && key.equals(k)))) 
58                 e = p; 
59 　　　 　　　　//若原來元素是紅黑樹節(jié)點揭蜒，調(diào)用紅黑樹的插入方法:putTreeVal
60             else if (p instanceof TreeNode) 
61                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
62             else {//證明原來的元素是鏈表的頭結(jié)點，從此節(jié)點開始向后尋找合適插入位置
63                 for (int binCount = 0; ; ++binCount) { 
64                     if ((e = p.next) == null) { 
65 　　　　　　　//找到插入位置后剔桨，新建節(jié)點插入
66                         p.next = newNode(hash, key, value, null); 
67 　　　　　　　//若鏈表上節(jié)點超過TREEIFY_THRESHOLD - 1屉更，將鏈表變?yōu)榧t黑樹
68                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
69                                 treeifyBin(tab, hash); 
70                         break; 
71 }
 72                     if (e.hash == hash &&
73                         ((k = e.key) == key || (key != null && key.equals(k)))) 
74                         break; 
75                     p = e; 
76 } 
77             }//end else
78             if (e != null) { // 待插入元素在　hashMap 中已存在
79                 V oldValue = e.value; 
80                 if (!onlyIfAbsent || oldValue == null) 
81                     e.value = value; 82 afterNodeAccess(e); 
83                 return oldValue; 
84 } 
85         }//end else
86         ++modCount; 
87         if (++size > threshold)
 88               resize(); 
89               afterNodeInsertion(evict); 
90         return null; 
91     }//end putval

 1        /*讀懂這個函數(shù)要注意理解 hash 沖突發(fā)生的幾種情況
 2          １、兩節(jié)點　key 值相同（hash值一定相同）洒缀，導(dǎo)致沖突
 3          ２瑰谜、兩節(jié)點　key 值不同，由于 hash 函數(shù)的局限性導(dǎo)致hash 值相同树绩，沖突
 4 　　 　　 ３萨脑、兩節(jié)點　key 值不同，hash 值不同饺饭，但 hash 值對數(shù)組長度取模后相同渤早，沖突
 5       */
 6         final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
 7                                        int h, K k, V v) { 
8             Class<?> kc = null;
 9             boolean searched = false; 
10             TreeNode<K,V> root = (parent != null) ? root() : this; 
11 　　　　　　　 //從根節(jié)點開始查找合適的插入位置（與二叉搜索樹查找過程相同）
12             for (TreeNode<K,V> p = root;;) { 
13                 int dir, ph; K pk; 
14                 if ((ph = p.hash) > h)
 15                     dir = -1;　//　dir小于０，接下來查找當(dāng)前節(jié)點左孩子
16                 else if (ph < h)
 17                     dir = 1;　//　dir大于０瘫俊，接下來查找當(dāng)前節(jié)點右孩子
18                 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 
19 　　　　　　　　　　　　//進(jìn)入這個else if 代表　hash 值相同鹊杖，key　相同
20                     return p; 
21 　　　　 　　　　 /*要進(jìn)入下面這個else if,代表有以下幾個含義: 
22                           1、當(dāng)前節(jié)點與待插入節(jié)點　key　不同,　hash 值相同 
23                           2扛芽、ｋ是不可比較的骂蓖，即ｋ并未實現(xiàn)　comparable<K>　接口
　　　　　　　　　　　　　　（若 k 實現(xiàn)了comparable<K>　接口川尖，comparableClassFor（k）返回的是ｋ的　class,而不是　null） 
24                 　　或者　compareComparables(kc, k, pk)　返回值為 0
　　　　　　　　　　　　　　(pk 為空　或者　按照 k.compareTo(pk) 返回值為０登下，
　　　　　　　　　　　　　　返回值為０可能是由于　ｋ的compareTo 方法實現(xiàn)不當(dāng)引起的，compareTo 判定相等被芳，而上個 else if　中　equals 判定不等)*/
25                 else if ((kc == null &&
26                           (kc = comparableClassFor(k)) == null) ||
27                          (dir = compareComparables(kc, k, pk)) == 0) { 
28                     //在以當(dāng)前節(jié)點為根的整個樹上搜索是否存在待插入節(jié)點（只會搜索一次）
29                     if (!searched) {
 30                         TreeNode<K,V> q, ch; 
31                         searched = true; 
32                         if (((ch = p.left) != null &&
33                              (q = ch.find(h, k, kc)) != null) ||
34                             ((ch = p.right) != null &&
35                              (q = ch.find(h, k, kc)) != null)) 
36 　　　　　　　　　　　　　　　　　//若樹中存在待插入節(jié)點银酬，直接返回
37                             return q; 
38 } 
39 　　　　　 　　　　　　 // 既然ｋ是不可比較的，那我自己指定一個比較方式
40                     dir = tieBreakOrder(k, pk); 
41                 }//end else if
42 
43                 TreeNode<K,V> xp = p; 
44                 if ((p = (dir <= 0) ? p.left : p.right) == null) { 
45 　　　　　　　　　　　　//找到了待插入的位置筐钟，xp 為待插入節(jié)點的父節(jié)點 
46 　　　　　　　　　　　　//注意TreeNode節(jié)點中既存在樹狀關(guān)系揩瞪，也存在鏈?zhǔn)疥P(guān)系，并且是雙端鏈表
47                     Node<K,V> xpn = xp.next; 
48                     TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 
49                     if (dir <= 0) 
50                         xp.left = x; 
51                     else
52                         xp.right = x; 
53                     xp.next = x; 
54                     x.parent = x.prev = xp; 
55                     if (xpn != null) 
56                         ((TreeNode<K,V>)xpn).prev = x;
 57 　　　　　　　　　　　　//插入節(jié)點后進(jìn)行二叉樹的平衡操作
58                           moveRootToFront(tab, balanceInsertion(root, x));
 59                     return null; 
60 } 
61             }//end for
62         }//end putTreeVal    　
63 　　
64 　　 　　static int tieBreakOrder(Object a, Object b) { 
65             int d; 
66             //System.identityHashCode()實際是利用對象 a,b 的內(nèi)存地址進(jìn)行比較
67             if (a == null || b == null ||
68                 (d = a.getClass().getName(). 
69                  compareTo(b.getClass().getName())) == 0) 
70                 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
71                      -1 : 1); 
72             return d; 
73         }

五篓冲、HashMap get 及其相關(guān)方法

1  　public V get(Object key) { 
2         Node<K,V> e; 
3 　　//實際上是根據(jù)輸入節(jié)點的 hash 值和 key 值利用getNode 方法進(jìn)行查找
4         return (e = getNode(hash(key), key)) == null ? null : e.value; 
5     }
6 　
 7 　final Node<K,V> getNode(int hash, Object key) { 
8         Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 
9         if ((tab = table) != null && (n = tab.length) > 0 &&
10             (first = tab[(n - 1) & hash]) != null) { 
11             if (first.hash == hash && // always check first node
12                 ((k = first.key) == key || (key != null && key.equals(k)))) 
13                 return first; 
14             if ((e = first.next) != null) { 
15                 if (first instanceof TreeNode) 
16 　　　　　　　　　　　　//若定位到的節(jié)點是　TreeNode 節(jié)點李破，則在樹中進(jìn)行查找
17                     return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
18                 do {//否則在鏈表中進(jìn)行查找
19                     if (e.hash == hash &&
20                         ((k = e.key) == key || (key != null && key.equals(k)))) 
21                         return e; 22                 } while ((e = e.next) != null); 
23 } 
24 } 
25         return null;
 26     }

 1         final TreeNode<K,V> getTreeNode(int h, Object k) {
 2 　　　　　　　　//從根節(jié)點開始，調(diào)用 find 方法進(jìn)行查找
 3             return ((parent != null) ? root() : this).find(h, k, null);
 4         }
 5 　
 6         final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
 7             TreeNode<K,V> p = this;
 8             do { 
9                 int ph, dir; K pk; 
10                 TreeNode<K,V> pl = p.left, pr = p.right, q;
11 　　　　　　　　　//首先進(jìn)行hash 值的比較壹将，若不同令當(dāng)前節(jié)點變?yōu)樗淖蠛⒆踊蛘哂液⒆?12                 if ((ph = p.hash) > h) 
13                     p = pl; 
14                 else if (ph < h) 
15                     p = pr; 
16 　　　　　　　　　//hash 值相同嗤攻，進(jìn)行 key　值的比較 
17                 else if ((pk = p.key) == k || (k != null && k.equals(pk))) 
18                     return p; 
19                 else if (pl == null) 
20                     p = pr; 
21                 else if (pr == null) 
22                     p = pl; 
23 　　　　　　　　　//執(zhí)行到這兒，意味著hash 值相同诽俯，key 值不同 
24    　　　　　　　　//若k 是可比較的并且k.compareTo(pk) 返回結(jié)果不為０可進(jìn)入下面elseif 
25                 else if ((kc != null ||
26                           (kc = comparableClassFor(k)) != null) &&
27                          (dir = compareComparables(kc, k, pk)) != 0) 
28                     p = (dir < 0) ? pl : pr; 
29                 /*若 k 是不可比較的　或者　k.compareTo(pk) 返回結(jié)果為０則在整棵樹中進(jìn)行查找妇菱，先找右子樹，右子樹沒有再找左子樹*/
30                 else if ((q = pr.find(h, k, kc)) != null) 
31                     return q; 
32                 else
33                     p = pl; 
34             } while (p != null); 
35             return null; 
36         }    

七暴区、HashMap 擴容方法　resize()

resize()　方法中比較重要的是鏈表和紅黑樹的 rehash 操作闯团，先來說下 rehash 的實現(xiàn)原理：

我們在擴容的時候，一般是把長度擴為原來2倍仙粱，所以房交，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置伐割『蛭叮看下圖可以明白這句話的意思，n為table的長度隔心，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例白群，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果硬霍。

元素在重新計算hash之后帜慢，因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)须尚，因此新的index就會發(fā)生這樣的變化：

因此崖堤，我們在擴充HashMap的時候侍咱，只需要看看原來的hash值新增的那個bit是1還是0就好了耐床，是0的話索引沒變，是1的話索引變成“原索引+oldCap”楔脯，可以看看下圖為16擴充為32的resize示意圖：

這個算法很巧妙撩轰，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認(rèn)為是隨機的堪嫂，因此resize的過程偎箫，均勻的把之前的沖突的節(jié)點分散到新的槽中了。

具體源碼介紹：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0;
　　/* 1皆串、resize（）函數(shù)在size　> threshold時被調(diào)用淹办。
            oldCap大于 0 代表原來的 table 表非空， oldCap 為原表的大小恶复，
            oldThr（threshold） 為 oldCap × load_factor*/
        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
 }/* 2怜森、resize（）函數(shù)在table為空被調(diào)用。
        oldCap 小于等于 0 且 oldThr 大于0谤牡，代表用戶創(chuàng)建了一個 HashMap副硅，但是使用的構(gòu)造函數(shù)為
        HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
        或 HashMap(Map<? extends K, ? extends V> m)，導(dǎo)致 oldTab 為 null翅萤，oldCap 為0恐疲，
        oldThr 為用戶指定的 HashMap的初始容量。*/
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;/* 3套么、resize（）函數(shù)在table為空被調(diào)用培己。
            oldCap 小于等于 0 且 oldThr 等于0，用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的　HashMap胚泌，所有值均采用默認(rèn)值漱凝，
       　　 oldTab（Table）表為空，oldCap為0诸迟，oldThr等于0茸炒，*/
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        } if (newThr == 0) { float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;        
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab; if (oldTab != null) {
　　　　　　　//把　oldTab 中的節(jié)點　reHash 到　newTab 中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e; if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
　　　　　　　　　　　　//若節(jié)點是單個節(jié)點，直接在 newTab　中進(jìn)行重定位
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;//若節(jié)點是　TreeNode 節(jié)點阵苇，要進(jìn)行 紅黑樹的 rehash　操作
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
　　　　　　　　　　　　//若是鏈表壁公，進(jìn)行鏈表的 rehash　操作
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next; do {
            　　                next = e.next;//根據(jù)算法　e.hash & oldCap　判斷節(jié)點位置　rehash　后是否發(fā)生改變
                            if ((e.hash & oldCap) == 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); if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        } if (hiTail != null) {
                            hiTail.next = null;
　　　　　　　　　　　　　　　　// rehash　后節(jié)點新的位置一定為原來基礎(chǔ)上加上　oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        } return newTab;
    } 

 1      //這個函數(shù)的功能是對紅黑樹進(jìn)行　rehash 操作
 2     final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 
 3             TreeNode<K,V> b = this;
 4             // Relink into lo and hi lists, preserving order
 5             TreeNode<K,V> loHead = null, loTail = null;
 6             TreeNode<K,V> hiHead = null, hiTail = null;
 7             int lc = 0, hc = 0;
 8     　　　　　//由于　TreeNode 節(jié)點之間存在雙端鏈表的關(guān)系，可以利用鏈表關(guān)系進(jìn)行 rehash
 9             for (TreeNode<K,V> e = b, next; e != null; e = next) { 
10                 next = (TreeNode<K,V>)e.next; 
11                 e.next = null; 
12                 if ((e.hash & bit) == 0) { 
13                     if ((e.prev = loTail) == null) 
14                         loHead = e; 
15                     else
16                         loTail.next = e; 
17                     loTail = e; 
18                     ++lc; 19 } 
20                 else { 
21                     if ((e.prev = hiTail) == null) 
22                         hiHead = e; 
23                     else
24                         hiTail.next = e; 
25                     hiTail = e; 
26                     ++hc; 
27 }
28 } 
29             
30             //rehash 操作之后注意對根據(jù)鏈表長度進(jìn)行　untreeify　或　treeify　操作
31             if (loHead != null) { 
32                 if (lc <= UNTREEIFY_THRESHOLD) 
33                     tab[index] = loHead.untreeify(map); 
34                 else { 
35                     tab[index] = loHead; 
36                     if (hiHead != null) // (else is already treeified)
37                   loHead.treeify(tab); 
38               } 
39             } 
40             if (hiHead != null) { 
41                 if (hc <= UNTREEIFY_THRESHOLD) 
42                     tab[index + bit] = hiHead.untreeify(map); 
43                 else { 
44                     tab[index + bit] = hiHead; 
45                     if (loHead != null) 46 hiHead.treeify(tab); 
47 } 
48             }//end if
49         }//end split
50         </pre>

參考文章：http://tech.meituan.com/java-hashmap.html
原文：https://www.cnblogs.com/Michaelwjw/p/6411176.html