做為面試常考的問題之一，每次都答的模模糊糊，有必要了解一下，首先來看一下hashmap的put方法的源碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public V put(K key, V value) { if (key == null) return putForNullKey(value); //將空key的Entry加入到table[0]中 int hash = hash(key.hashCode()); //計算key.hashcode()的hash值，hash函數由hashmap自己實現 int i = indexFor(hash, table.length);//獲取將要存放的數組下標 /* * for中的代碼用于：當hash值相同且key相同的情況下，使用新值覆蓋舊值（其實就是修改功能） */ for (Entry<K, V> e = table[i]; e != null; e = e.next) {//注意：for循環在第一次執行時就會先判斷條件 Object k; //hash值相同且key相同的情況下，使用新值覆蓋舊值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //e.recordAccess(this); return oldValue;//返回舊值 } } modCount++; addEntry(hash, key, value, i);//增加一個新的Entry到table[i] return null;//如果沒有與傳入的key相等的Entry，就返回null }/** * "按位與"來獲取數組下標 */ static int indexFor(int h, int length) { return h & (length - 1); } |
hashmap始終將自己的桶保持在2的n次方，這是為什么？indexFor這個方法解釋了這個問題
大家都知道計算機里面位運算是基本運算，位運算的效率是遠遠高于取余%運算的
舉個例子：
2^n轉換成二進制就是1+n個0，減1之后就是0+n個1，如16 -> 10000，15 -> 01111
那么根據&位運算的規則，都為1(真)時，才為1，那0≤運算后的結果≤15，假設h <= 15，那么運算后的結果就是h本身，h >15，運算后的結果就是最后四位二進制做&運算后的值，最終，就是%運算后的余數。
當容量一定是2^n時，h & (length - 1) == h % length
補充知識：HashMap容量和負載因子
HashMap底層數據結構是數組+鏈表，JDK1.8中還引入了紅黑樹，當鏈表長度超過8個時，會將鏈表轉成紅黑樹，以提升其查找性能。那么，給出一個<key, value>節點，HashMap是如何確定這個節點應該放在具體哪個位置呢？（以JDK1.8為例）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // HashMap沒有被初始化，則先進行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 節點所在index = (n - 1) & hash，該位置沒有數據，則直接將新節點放在數組的index位置上 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // index上已經有節點了 Node<K,V> e; K k; // 如果新key與原來的key一樣，則e指向原節點p（后面會用新value替換e所指向的value） if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果該節點是樹節點，則采用樹的插入算法，插入新節點 else if (p instanceof HashMap.TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 該節點是鏈表節點 for (int binCount = 0; ; ++binCount) { // 將新節點插入到index所在鏈表的末端 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 鏈表節點超過8個，則進行鏈表轉樹處理 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 同樣的，如果key已經存在的話，則不進行插入操作，而是后面進行value替換 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // e != null的情況，就是key已經存在了，這里統一進行了新值value，替換舊值e.value的操作 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 插入后數組size 大于閾值的話，需要進行擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;} |
看源碼，節點落在數組中的index = （數組長度 - 1） & key的hashcode，如果該index上沒有數據，則直接插到該index上，如果節點已經有數據了，則把新節點插入該index對應的鏈表中（如果鏈表節點大于8個，會進行鏈表轉樹，之后的插入算法就變成了樹的插入算法）。
每次put之后，會檢測一下是否需要擴容，size超過了 總容量 * 負載因子，則會擴容。默認情況下，16 * 0.75 = 12個。
1、為什么初始容量是16
當容量為2的冪時，上述n -1 對應的二進制數全為1，這樣才能保證它和key的hashcode做&運算后，能夠均勻分布，這樣才能減少hash碰撞的次數。至于默認值為什么是16，而不是2 、4、8，或者32、64、1024等，我想應該就是個折中處理，過小會導致放不下幾個元素，就要進行擴容了，而擴容是一個很消耗性能的操作。取值過大的話，無疑會浪費更多的內存空間。因此在日常開發中，如果可以預估HashMap會存入節點的數量，則應該在初始化時，指定其容量。
2、為什么負載因子是0.75
也是一個綜合考慮，如果設置過小，HashMap每put少量的數據，都要進行一次擴容，而擴容操作會消耗大量的性能。如果設置過大的話，如果設成1，容量還是16，假設現在數組上已經占用的15個，再要put數據進來，計算數組index時，發生hash碰撞的概率將達到15/16，這違背的HashMap減少hash碰撞的原則。
以上這篇談談Hashmap的容量為什么是2的冪次問題就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/wanghuan220323/article/details/78242449
