java hashmap扩容大小_HashMap的扩容机制以及默认大小为何是2次幂
HashMap的Put方法
HashMap的數據結構設計可以參考鏈接。接下來回顧HashMap的put(Key k, Value v)過程：
(1)對 Key求Hash值，計算出Hash表下標，對應hashCode()方法，所以使用class對象作為Key時需要重寫該對象的hashCode()方法與equals()方法。
(2)如果沒有碰撞，直接放入桶中，即Hash表數組對應位置的鏈表表頭。
(3)如果碰撞了，若節點已經存在就替換舊值，否則以鏈表的方式將該元素鏈接到后面。
(4)如果鏈表長度超過閥值(TREEIFY_THRESHOLD == 8)，就把鏈表轉成紅黑樹。紅黑樹我不熟悉，這里不展開講。
(5)如果桶滿了(容量 * 加載因子)，就需要resize。
HashMap的擴容機制
假設length為Hash表數組的大小，方法indexFor(int hash, int length)為
indexFor(int hash, int length) {
return hash % length;
}
在舊數組中同一條Entry鏈上的元素，在resize過程中，通過重新計算索引位置后，有可能被放到了新數組的不同位置上。JDK8做了一些優化，resize過程中對Hash表數組大小的修改使用的是2次冪的擴展(指長度擴為原來2倍)，這樣有2個好處。
好處1
在hashmap的源碼中。put方法會調用indexFor(int h, int length)方法，這個方法主要是根據key的hash值找到這個entry在Hash表數組中的位置，源碼如下：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
上述代碼也相當于對length求模。 注意最后return的是h&(length-1)。如果length不為2的冪，比如15。那么length-1的2進制就會變成1110。在h為隨機數的情況下，和1110做&操作。尾數永遠為0。那么0001、1001、1101等尾數為1的位置就永遠不可能被entry占用。這樣會造成浪費，不隨機等問題。 length-1 二進制中為1的位數越多，那么分布就平均。
好處2
以下圖為例，其中圖(a)表示擴容前的key1和key2兩種key確定索引位置的示例，圖(b)表示擴容后key1和key2兩種key確定索引位置的示例，n代表length。
元素在重新計算hash之后，因為n變為2倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：
resize過程中不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖(一方面位運算更快，另一方面抗碰撞的Hash函數其實挺耗時的)：
源碼如下
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 // 超過最大值就不再擴充了，就只好隨你碰撞去吧
8 if (oldCap >= MAXIMUM_CAPACITY) {
9 threshold = Integer.MAX_VALUE;
10 return oldTab;
11 }
12 // 沒超過最大值，就擴充為原來的2倍
13 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
14 oldCap >= DEFAULT_INITIAL_CAPACITY)
15 newThr = oldThr << 1; // double threshold
16 }
17 else if (oldThr > 0) // initial capacity was placed in threshold
18 newCap = oldThr;
19 else { // zero initial threshold signifies using defaults
20 newCap = DEFAULT_INITIAL_CAPACITY;
21 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
22 }
23 // 計算新的resize上限
24 if (newThr == 0) {
25
26 float ft = (float)newCap * loadFactor;
27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28 (int)ft : Integer.MAX_VALUE);
29 }
30 threshold = newThr;
31 @SuppressWarnings({"rawtypes"，"unchecked"})
32 Node[] newTab = (Node[])new Node[newCap];
33 table = newTab;
34 if (oldTab != null) {
35 // 把每個bucket都移動到新的buckets中
36 for (int j = 0; j < oldCap; ++j) {
37 Node e;
38 if ((e = oldTab[j]) != null) {
39 oldTab[j] = null;
40 if (e.next == null)
41 newTab[e.hash & (newCap - 1)] = e;
42 else if (e instanceof TreeNode)
43 ((TreeNode)e).split(this, newTab, j, oldCap);
44 else { // 鏈表優化重hash的代碼塊
45 Node loHead = null, loTail = null;
46 Node hiHead = null, hiTail = null;
47 Node next;
48 do {
49 next = e.next;
50 // 原索引
51 if ((e.hash & oldCap) == 0) {
52 if (loTail == null)
53 loHead = e;
54 else
55 loTail.next = e;
56 loTail = e;
57 }
58 // 原索引+oldCap
59 else {
60 if (hiTail == null)
61 hiHead = e;
62 else
63 hiTail.next = e;
64 hiTail = e;
65 }
66 } while ((e = next) != null);
67 // 原索引放到bucket里
68 if (loTail != null) {
69 loTail.next = null;
70 newTab[j] = loHead;
71 }
72 // 原索引+oldCap放到bucket里
73 if (hiTail != null) {
74 hiTail.next = null;
75 newTab[j + oldCap] = hiHead;
76 }
77 }
78 }
79 }
80 }
81 return newTab;
82 }
Reference
https://zhidao.baidu.com/question/1738414783693877787.html
https://blog.csdn.net/aichuanwendang/article/details/53317351
轉載至鏈接:https://my.oschina.net/keyven/blog/1840583
總結
以上是生活随笔為你收集整理的java hashmap扩容大小_HashMap的扩容机制以及默认大小为何是2次幂的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java filechannel api
- 下一篇： linux centos升级php_Ce