JDK 的 HashMap 中使用了一個 hash 方法來做 bit shifting，在注釋中說明是為了防止一些實現比較差的hashCode() 方法，請問原理是什么？JDK 的源碼參見：GrepCode: java.util.HashMap (.java)
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
PS：網上看見有人說作者本人說原理需要參見圣經《計算機程序設計藝術》的 Vol.3 里頭的介紹，不過木有看過神書，求達人介紹
這段代碼叫“擾動函數”。
題主貼的是Java 7的HashMap的源碼，Java 8中這步已經簡化了，只做一次16位右位移異或混合，而不是四次，但原理是不變的。下面以Java 8的源碼為例解釋，
//Java 8中的散列值優化函數staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);//key.hashCode()為哈希算法，返回初始哈希值}
大家都知道上面代碼里的key.hashCode()函數調用的是key鍵值類型自帶的哈希函數，返回int型散列值。理論上散列值是一個int型，如果直接拿散列值作為下標訪問HashMap主數組的話，考慮到2進制32位帶符號的int表值范圍從-2147483648到2147483648。前后加起來大概40億的映射空間。只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，內存是放不下的。你想，HashMap擴容之前的數組初始大小才16。所以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的余數才能用來訪問數組下標。源碼中模運算是在這個indexFor( )函數里完成的。
bucketIndex = indexFor(hash, table.length);indexFor的代碼也很簡單，就是把散列值和數組長度做一個"與"操作，
static int indexFor(int h, int length) { return h & (length-1);}順便說一下，這也正好解釋了為什么HashMap的數組長度要取2的整次冪。因為這樣（數組長度-1）正好相當于一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度16為例，16-1=15。2進制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。
10100101 11000100 00100101& 00000000 00000000 00001111---------------------------------- 00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數列的漏洞，恰好使最后幾個低位呈現規律性重復，就無比蛋疼。這時候“擾動函數”的價值就體現出來了，說到這里大家應該猜出來了。看下面這個圖，
右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。最后我們來看一下PeterLawley的一篇專欄文章《An introduction to optimising a hashing strategy》里的的一個實驗：他隨機選取了352個字符串，在他們散列值完全沒有沖突的前提下，對它們做低位掩碼，取數組下標。
結果顯示，當HashMap數組長度為512的時候，也就是用掩碼取低9位的時候，在沒有擾動函數的情況下，發生了103次碰撞，接近30%。而在使用了擾動函數之后只有92次碰撞。碰撞減少了將近10%。看來擾動函數確實還是有功效的。但明顯Java 8覺得擾動做一次就夠了，做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。
------------------------------------------------------
https://www.zhihu.com/question/20733617