經典面試題之HashMap(二)

三 不考慮內存限制，HashMap可以無限存儲數據嗎？

不可以，HashMap是有最大容量上限的。我們還是來看下源碼註釋：

<code>/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;/<code>

很明顯，如果構造函數傳入的值大於MAXIMUM_CAPACITY ，那麼替換成該數 MAXIMUM_CAPACITY 是 1 << 30 即 2的30次方。

為什麼是1 << 30？ 1 <<31 不行嗎？

注意看這個值是int 類型的。我們知道int 的極限最大值 Integer.MAX_VALUE 是2的31次方減1，即2147483647，如果 1 << 30 改為 1 << 31 ，由於int是有符號數，這個值將為 -2147483648，而且hashMap的容量都是2的整數次冪，也就只能是2的30次方了。然而這並不是HashMap的最大容量。

來看下HashMap的構造函數

<code> public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) 

            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
/<code>

上面代碼中有一句

<code>if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;/<code>

如果我要存的數目大於 MAXIMUM_CAPACITY，你還把我的容量縮小成 MAXIMUM_CAPACITY？其實不是的，在resize()方法中有一句

<code> if (oldCap >= MAXIMUM_CAPACITY) {               
   threshold = Integer.MAX_VALUE;                
   return oldTab;            
 }/<code>

在這裡我們可以看到其實 hashmap的“最大容量“是Integer.MAX_VALUE;

threshold=capacity*loadFactor threshold 表示當HashMap的size大於threshold時會執行resize操作。size就是HashMap中實際存在的鍵值對數量。

思考題：如果到達了HashMap的容量上限，再繼續添加元素，會怎樣？

其實你可以計算一下，當HashMap到達容量上限後佔用的內存大小，已經很大了，所以一般情況下是內存溢出，我們在日常使用時，一般情況下不會把那麼大的數據全部放到一個HashMap中。然而如果不考慮內存溢出的情況，就是你有一個超大的內存，那這個時候會怎樣？

四 如何確定哈希桶數組索引位置？

我們首先想到的就是把hash值對數組長度取模運算，這樣一來，元素的分佈相對來說是比較均勻的。但是，模運算的消耗還是比較大的，在HashMap中是這樣做的：調用下面的代碼來計算該對象應該保存在table數組的哪個索引處。

<code>static int indexFor(int h, int length) {      
  //jdk1.7的源碼，jdk1.8沒有這個方法，但是實現原理一樣的     
  return h & (length-1);    //第三步 取模運算
}/<code>

這個方法非常巧妙，它通過h & (table.length -1)來得到該對象的保存位，而HashMap底層數組的長度總是2的n次方，這是HashMap在速度上的優化。當length總是2的n次方時，h& (length-1)運算等價於對length取模，也就是h%length，但是&比%具有更高的效率。

注意 h& (length-1) 當且僅當length(即capacity)是2的整倍數的時候才等於 h % length ,從這個角度也說明了capacity為什麼一定要用2的整次冪。

數組長度-1 正好相當於一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度16為例，16-1=15。2進製表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。

五 瞭解HashMap的hash函數嗎？

我們先來說說hash算法的一般實現：

• 大數變小數-->取模
• 讓結果的規律性不明顯--> 異或、改變原始數據、移位
• 碰撞是存在的，主要是看解決碰撞的方案

java中常用的hashCode算法

• Object類的hashCode。返回對象的經過處理後的內存地址。由於每個對象的內存地址都不一樣，所以哈希碼也不一樣，這是個native方法。取決於JVM的內部設計，一般是某種C地址的偏移。
• String 類的hashCode,根據String類包含的字符串的內容，根據一種特殊的算法返回哈希碼，只要字符串的內容相同，返回的哈希碼也相同。
• Integer 等包裝類，返回的哈希碼就是Integer對象裡所包含的那個整數的值，例如 Integer i1 = new Integer(100), i1.hashCode() 的值就是 100。由此可見，兩個一樣大小的Integer對象，返回的哈希碼也一樣。
• int、char這樣的基礎類，它們不需要hashCode,如果需要存儲時，將進行自動裝箱操作，計算方法同上。

我們來看下HashMap中的hash算法是如何實現的：

<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)？

我們通過上文了解了HashMap如何計算出數組索引位置，但其實有一個問題，就是即使我的散列值分佈再鬆散，要是隻取最後幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分佈上成等差數列的漏洞，恰好使最後幾個低位呈現規律性重複，就無比蛋疼。

這時候“擾動函數”的價值就體現出來了

右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的信息也被變相保留下來。這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。（JDK 7做了4次右移，估計是邊際效應的原因，JDK8就只做了一次右移）

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

閱讀更多 小盒子的技術分享 的文章

關鍵字: 面試題 人生第一份工作 經典