回答這個問題,我們首先需要知道HashMap是如何存取元素的,為了存取高效,需要把數據分布均勻,這我們就需要分析HashMap的源碼,從底層上理解Java作者的意圖。
HashMap如何存放元素
HashMap存放元素時通過put()方法來實現的,我們知道定位元素的存放位置,是通過key的hash值,做一定的運算來確定的,而HashMap中的hash()方法,就是來獲取hash值的源碼如下。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
這裡計算的hash值,並不是直接使用key.hashCode()來獲取的值h(後面統一稱為h),而是用h與h無符號右移的值做異或運算。
h >>> 16 這裡先解釋下這句話什麼意思,>>>其實是無符號右移,什麼意思呢,我們看下圖就明白了。
將h轉換成二進位數,然後無符號右移16位,空缺的用0補齊,看圖中字體顏色我們就能清楚地明白這是怎麼操作的。
h^ (h >>> 16)的作用
想要知道寫HashMap源碼大佬的想法,我們還需要來看看HashMap中put()方法的源碼。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //通過位運算找到數組中的下標位置,如果數組中對應下標為空,則可以直接存放下去 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); ......省略 }
我們從源碼中可以看出來,計算下標的時候,是通過(n - 1) & hash來計算的,n = tab.length是HashMap的容量,用HashMap容量減1與hash值做&運算,得出下標值。
HashMap默認初始容量位16,16-1=15,15的二進位為00000000 00000000 00001111,與hash值做&運算時,結果是只取了最低的後四位,hash值的高位全部歸0,只保留了低位值。有的同學,可能不太清楚什麼意思,我們舉個例子,畫個圖就清楚了。
假如有個key的hash值,轉化為二進位是,01001001 00110010 00011001,獲取元素下標時,用HashMap容量減1的二進位與hash值的二進位做&運算,如下圖所示。
我們可以看到hash值二進位的高位都補0了,其實上面的計算可以簡化為 1111 & 1001,結果為1001,轉換成十進位就是9,即下標為9。
當HashMap容量為16=2的4次方時,則是後4位參與&運算當HashMap容量為32=2的5次方時,則是後5位參與&運算當HashMap容量為2時,則是後n位參與&運算,獲取元素下標。 因為在大多數情況下,HashMap的容量是小於2的16次方,運算得到的下標都是與hashcode的二進位的後16位做&運算的到的值。
要想得到的hash值更加的散列,我們需要把高位和低位都參與運算,這樣的算出的hash值,更有特徵。如果直接返回hash值,獲取元素下標值,參與取模運行的低位,重複性偏高,將高16位和低16位做&運算,這樣算出來的hash值,更加分散,hash碰撞的概率就越小,所以就有了h^(h>>>16)。
HashMap容量為2的作用
我們知道HashMap底層由數組+(鍊表或紅黑樹)來實現,元素都被存放在一個個Entry數組中,存放元素的時候,會根據HashMap中hash()方法計算key的hash值,再根據計算出的hash值,確定元素存到數組的哪個位置,即下標值,一般HashMap的容量不會太大,而hash值並不能直接作為下標值,所以一般根據HashMap的容量減1來取模計算下標值(PS:上面已經介紹了具體做法)。
當容量為2時,取模的是時候,h&(n-1)與h%n計算的結果相等,而&運算的效率遠遠比用%效率更高,因為&是直接對內存中的二進位碼進行操作,不需要轉換為十進位,所以更快。計算下標值的公式為h&(n-1),當容量為奇數時,n-1則為偶數,轉換成二進位,最後一位一定是0,在做&運算計算下標值時,最後一位也一定是0,則奇數位的下標值,則無法取到,如3(0011), 5(0101),7(0111)等,所以容量為偶數時,才能取到奇數下標值。
總結
HashMap的容量為2主要目的還是為了讓元素均勻分布,減少hash碰撞。從HashMap中的hash()方法就知道,讓高位和低位都參與運算,讓hash值更有特徵性,在通過計算的hash值,與容量減一做&運算得到下標值,綜合分析,當容量為2時,元素存放更均勻,效率也更快。