HashMap 是後端面試的常客，比如默認初始容量是多少？加載因子是多少？是線程非安全的嗎？put 操作過程複述下？get 操作複述下？在 jdk 1.7 和 1.8 實現上有什麼不同？等等一系列問題，可能這些問題你都能對答如流，說明對 HashMap 還是比較理解的，但最近我們團隊的同學做了一個技術分享，其中有幾點我挺有收穫的，我給大家分享下
我們每週五都會進行技術分享，大家輪流分享，其實這種機制挺好的，大家坐在一起深入討論一個知識點，進行思維的碰撞，多贏
拋出兩個問題，看你能否回答出來？
1. 如何找到比設置的初始容量值大的最小的 2 的冪次方整數？
2. HashMap 中對 key 做 hash 處理時，做了什麼特殊操作？為什麼這麼做？
先自己思考下，再往下閱讀效果更佳哦！
下面的分析都是針對 jdk 1.8
分析
問題1：如何找到比設置的初始容量值大的最小的 2 的冪次方整數？
我們在用 HashMap 的時候，如果用默認構造器，就會建一個初始容量為 16，加載因子為 0.75 的 HashMap。這樣做有個缺點，就是在數據量比較大的時候，會進行頻繁的擴容操作，擴容會發生數據的移位，為了避免擴容，提高性能，我們習慣預估下容量，然後通過帶容量的構造器創建，看下源碼
~~~ javapublic HashMap(int initialCapacity, float loadFactor) {...// 如果設置的初始容量大於最大容量就默認為最大容量 2^30
if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;...this.loadFactor = loadFactor;// tableSizeFor 方法主要就是計算比給定的初始容量值大的最小的 2 的冪次方整數this.threshold = tableSizeFor(initialCapacity);}~~~
通過源碼我們可知，容量最大值為 2^30，也就是說 HashMap 的數組部分的長度的範圍為[0,2^30]，然後計算比初始容量大的最小的2的冪次方整數，其中 **tableSizeFor** 方法是重點，我們看下源碼
~~~ java// Returns a power of two size for the given target capacitystatic final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n<0) ? 1 : (n >= MAXIMUM CAPACITY) ? MAXIMUM CAPACITY : n + 1;}~~~
這個方法設計的非常巧妙，因為 HashMap 要保證容量是 2 的整數次冪，該方法實現的效果就是如果你輸入的 cap 本身就是 2 的整數次冪，那麼就返回 cap 本身，如果輸入的 cap 不是 2 的整數次冪，返回的就是比 cap 大的最小的 2 的整數次冪
為什麼容量要是 2 的整數次冪？
因為獲取 key 在數組中對應的下標是通過 key 的哈希值與數組長度 -1 進行與運算，如：tab[i = (n - 1) & hash]
1. n 為 2 的整數次冪，這樣 n-1 後之前為 1 的位後面全是 1，這樣就能保證 (n-1) & hash 後相應的位數既可能是 0 又可能是 1，這取決於 hash 的值，這樣能保證散列的均勻，同時與運算效率高
2. 如果 n 不是 2 的整數次冪，會造成更多的 hash 衝突
該方法首先執行了 cap -1 操作，這樣做的好處是避免輸入的 cap 是 2 的整數次冪，最後計算的數是 cap 的 2 倍的情況，因為設置 cap 已經滿足 HashMap 的要求了，沒有必要初始化一個 2 倍容量的 HashMap 了，看不明白不急後面有示例分析
前面我們已經介紹 HashMap 的最大容量為 2^30，所以容量最大就是 30 bit 的整數，我們就用 30 位的一個數演示下算法中的移位取或操作，假設 n = 001xxx xxxxxxxx xxxxxxxx xxxxxxxx （x 代表該位上是 0 還是 1 我們不關心）
第一次右移 n |= n >>> 1 ，該操作是用 n 本身 和 n 右移 1 位後的數進行或操作，這樣可以實現把 n 的最高位的 1 緊鄰的右邊一位也置為 1
~~~n 001xxx xxxxxxxx xxxxxxxx xxxxxxxxn >>> 1 0001xx xxxxxxxx xxxxxxxx xxxxxxxx| 或操作 0011xx xxxxxxxx xxxxxxxx xxxxxxxx結果就是把 n 的最高位為 1 的緊鄰的右邊的 1 位也置為了 1，這樣高位中有連續兩位都是 1~~~
第二次右移 n |= n >>> 2
~~~n 0011xx xxxxxxxx xxxxxxxx xxxxxxxxn >>> 2 000011 xxxxxxxx xxxxxxxx xxxxxxxx| 或操作 001111 xxxxxxxx xxxxxxxx xxxxxxxx結果就是 n 的高位中有連續 4 個 1~~~
第三次右移 n |= n >>> 4
~~~n 001111 xxxxxxxx xxxxxxxx xxxxxxxxn >>> 4 000000 1111xxxx xxxxxxxx xxxxxxxx| 或操作 001111 1111xxxx xxxxxxxx xxxxxxxx結果就是 n 的高位中有連續 8 個 1~~~
第四次右移 n |= n >>> 8
~~~n 001111 1111xxxx xxxxxxxx xxxxxxxxn >>> 8 000000 00001111 1111xxxx xxxxxxxx| 或操作 001111 11111111 1111xxxx xxxxxxxx結果就是 n 的高位中有連續 16 個 1~~~
第五次右移 n | n >>> 16
~~~n 001111 11111111 1111xxxx xxxxxxxxn >>> 16 000000 00000000 00001111 11111111| 或操作 001111 11111111 11111111 11111111結果就是 n 的高位1後面都置為 1~~~
最後會對 n 和最大容量做比較，如果 >= 2^30，就取最大容量，如果<2^30 ，就對 n 進行 +1 操作，因為後面位數都為1，所以 +1 就相當於找比這個數大的最小的 2的整數次冪
011111 11111111 11111111 11111111，這個值就是比給的值大的最小的 2 的整數次冪
下面我們用一個具體說演示下，比如 cap = 18
我們輸入的是 18，輸出的是 32，正好是比 18 大的最小的 2 整數次冪
如果 cap 本身就為 2的整數次冪，輸出結果為什麼？
通過演示可見，cap 本身就是 2 的整數次冪的輸出結果為其本身
上面還遺留了個問題，就是先對 cap -1，我解釋說為了避免輸出的是偶數，最後計算的結果為 2*cap，浪費空間，看下面的演示
通過演示，我們可以看出，輸入的是 16，最後計算的結果卻是 32，這就會浪費空間了，所以說算法很牛，先對 cap 做了減一操作
問題2：HashMap 中對 key 做 hash 處理時，做了什麼特殊操作？為什麼這麼做？
首先我們知道 HashMap 在做 put 操作的時候，會先對 key 做 hash 操作，直接定位到源碼位置
~~~javastatic final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}~~~
可以看到再對 key 做 hash 操作時，執行了 (h = key.hashCode()) ^ (h >>> 16)
~~~原 hashCode 值: 10110101 01001100 10010101 11011111右移 16 位後的值: 00000000 00000000 10110101 01001100異或後的值： 10110101 01001100 00100000 10010011~~~
這個操作是把 key 的 hashCode 值與 hashCode 值右移 16 位做 異或（不同為 1，相同為 0），這樣就是把哈希值的高位和低位一起混合計算，這樣就能使生成的 hash 值更離散
這裡需要我解釋下，通過前面的介紹，我們知道數組的容量範圍是 [0,2^30]，這個數還是比較大的，平時使用的數組容量還是比較小的，比如默認的大小 16，假設三個不同的 key 生成的 hashCoe 值如下所示：
19305951 00000001 00100110 10010101 11011111
128357855 00000111 10100110 10010101 11011111
38367 00000000 00000000 10010101 11011111
他們三個有個共同點是低 16 位完全一樣，但高 16 位不同，當計算他們在數組中所在的下標時，通過 (n-1)&hash，這裡 n 是 16，n-1=15,15 的二進制表示為
00000000 00000000 00000000 00001111
用 19305951、128357855、38367 都與 15 進行 & 運算，結果如下
通過計算後發現他們的結果一樣，也就是說他們會被放到同一個下標下的鏈表或紅黑樹中，顯然不符合我們的預期
所以對 hash 與其右移 16 位後的值進行異或操作，然後與 15 做與運算，看 hash 衝突情況
可見經過右移 16位後再進行異或操作，然後計算其對應的數組下標後，就被分到了不同的桶中，解決了哈希碰撞問題，思想就是把高位和低位混合進行計算，提高分散性
最後
覺得還不錯的話可以關注轉發支持一波哦~
閱讀更多 程序媛拾玖 的文章
