理論上 hash 散列是一個 int 值，如果直接拿出來作為下標訪問 hashmap 的話，考慮到二進制 32 位，取值范圍在-2147483648 ~ 2147483647。大概有 40 億個 key ， 只要哈希函數映射比較均勻松散，一般很難出現碰撞。
計算過程
以下代碼叫做 “擾動函數”
//java 8 中的散列值優化函數
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
理論上 hash 散列是一個 int 值，如果直接拿出來作為下標訪問 hashmap 的話，考慮到二進制 32 位，取值范圍在-2147483648 ~ 2147483647。大概有 40 億個 key ， 只要哈希函數映射比較均勻松散，一般很難出現碰撞。
一個客觀的問題：要存下 40 億長度的數組，服務器內存是不能放下的。通常咱們 HashMap 的默認長度為 16 。所以這個 hashCode , (key.hashCode ) 是不能直接來使用的。使用之前先做對數組長度的與運算，得到的值才能用來訪問數組下標。
代碼如下：
// n = hashmap 的長度
p = tab[i = (n - 1) & hash])
這里為什么要使用 n -1 ，來進行與運算，這里詳單與是一個”低位掩碼”, 以默認長度 16 為例子。和某個數進行與運算，結果的大小是 < 16 的。如下所示：
10000000 00100000 00001001
& 00000000 00000000 00001111
------------------------------
00000000 00000000 00001001 // 高位全部歸 0, 只保留后四位
這個時候會有一個問題，如果本身的散列值分布松散，只要是取后面幾位的話，碰撞也會非常嚴重。還有如果散列本身做得不好的話，分布上成等差數列的漏洞，可能出現最后幾位出現規律性的重復。
這個時候“擾動函數”的價值就體現出來了。如下所示：
在 hash 函數中有這樣的一段代碼：(h = key.hashCode()) ^ (h >>> 16) 右位移 16 位， 正好是32bit 的一半，與自己的高半區做成異或，就是為了混合原始的哈希碼的高位和低位，以此來加大低位的隨機性。并且混合后的低位摻雜了高位的部分特征，這樣高位的信息變相保存下來。其實按照開發經驗來說絕大多數情況使用的時候 HashMap 的長度不會超過 1000，所以提升低位的隨機性可以提升可以減少 hash 沖突，提升程序性能。
如果感興趣的小伙伴可以瀏覽下一下 Peter Lawlay 的專欄《An introduction to optimising a hashing strategy》的一個實驗：他隨機選取了 352 個字符串，在散列值完全沒有沖突的前提下，對低位做掩碼，取數組下標。
結果顯示， 當 hashmap 的數組長度為 512 的時候，也就是采用低位掩碼取低 9 位的時候，在沒有擾動函數的情況下，發生了 103 次碰撞，接近 30%。而在使用擾動函數之后只有 92 次碰撞。碰撞減少了將近10%。說明擾動函數確實有功效的。
但是明顯 Java 8 覺得擾動做一次就夠用了，做 4 次的話，可能邊際效用也不大， 為了效率考慮就改成了一次。
代碼演示?
import java.lang.reflect.Field;
import java.util.HashMap;
/**
* HashMap 計算 hashKey
* <p>
* 演示：擾動函數
*
* @see HashMap#hash(Object)
*/
public class HashKeyTest {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
HashMap<String, String> map = new HashMap<>();
String k = "王羲之";
String v = "大書法家";
map.put(k, v);
Field field = map.getClass().getDeclaredField("table");
field.setAccessible(Boolean.TRUE);
Object[] nodes = (Object[]) field.get(map);
int h = k.hashCode();
System.out.println(" h=" + h);
System.out.println();
// 調用 hashCode 結果
System.out.println(" h=hashCode() " + num0x(h) + " 調用 hashCode");
// 無符號右移 16
System.out.println(" h>>>16 " + num0x(h >>> 16));
System.out.println("--------------------------------------------------");
// 計算 hash
System.out.println(" hash=h^(h>>>16) " + num0x(h ^ (h >>> 16)) + " 計算 hash");
System.out.println("--------------------------------------------------");
// 計算下標
System.out.println(" (n-1)&hash " + num0x(15 & (h ^ (h >>> 16))) + " 計算下標");
System.out.println();
int idx = (15 & (h ^ (h >>> 16)));
// 輸出下標
System.out.println(" 下標: " + idx);
// 在下標中去獲取數據
System.out.println(" 查詢結果:" + nodes[idx]);
}
/**
* 輸入 int 轉換為 二進制字符串
*
* @param num 數字
* @return 二進制字符串
*/
static String num0x(int num) {
String num0x = "";
for (int i = 31; i >= 0; i--) {
num0x += (num & 1 << i) == 0 ? "0" : "1";
}
return num0x;
}
}
運行結果如下：
參考資料：https://www.zhihu.com/question/20733617
