HashMap中的算法

hash(Object key)

<code>static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }/<code>

hash(Object key)的作用就是重新計算hash值。

問題：HashMap中為什麼不直接用key.hashCode()獲取哈希值，而是使用(h = key.hashCode()) ^ (h >>> 16)？

解析： (h = key.hashCode()) ^ (h >>> 16)這樣寫有點類似重寫了hashCode，確保得出的數足夠的隨機，因為進行hash計算的時候 確保它的數足夠的分散，以便於計算數組下標的時候存放的值足夠分散。

深入理解：HashMap的put方法中計算哈希桶數組索引位置時代碼為

<code>(n - 1) & hash //hash值與(數組長度-1)進行取模運算/<code>

因為hash返回的結果為int，int是32位的。在put的時候有很多的數據就會分配的比較集中。

key的hash值高16位不變，低16位與高16位異或作為key的最終hash值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此key的hash值高16位不變

為什麼要這麼幹呢？這個與HashMap中table下標的計算有關。

當HashMap容量為默認容量16時：

只有hash值的低4位參與了運算。這樣做很容易產生碰撞。設計者權衡了speed, utility, and quality，將高16位與低16位異或來減少這種影響。設計者考慮到現在的hashCode分佈的已經很不錯了，而且當發生較大碰撞時也用樹形存儲降低了衝突。僅僅異或一下，既減少了系統的開銷，也不會造成的因為高位沒有參與下標的計算(table長度比較小時)，從而引起的碰撞。

備註：^ ：按位異或就是把兩個數按二進制，相同就取0，不同就取1<<< ：無符號右移參考文章：https://blog.csdn.net/fan2012huan/article/details/51097331

tableSizeFor(int cap)

核心思想

<code>將該數的低位二進制位全部變為1， 並加1返回。/<code>

<code>  static 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;    }/<code>

以上算法實現的目的是查找一個數最近比它大的2的冪。 例子： tableSizeFor(17) = 32 tableSizeFor(28) = 32

閱讀更多 陳小亮 的文章

關鍵字: 算法 按位 異或