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