Java集合之一——HashMap（辨析）

看到一篇講hashmap的文章，講的很不錯，但是有一點我覺得作者沒有講清楚，這裡我說一下自己的理解。

原文，先看原文：

https://blog.csdn.net/woshimaxiao1/article/details/83661464

前文概述，該博客的主要內容如下：

1. 什麼是哈希表（主幹為數組）、什麼是哈希衝突、如何解決哈希衝突。這些大都是數據結構的基礎知識，這裡不再贅述

2.hashmap的實現原理：

簡要概述一下：

主幹是數組，衝突用鏈表解決。

每個元素其實都一個entry對象。

預設容量為16，負載因數0.75，當前元素數量大於等於容量*負載因數，擴容。

擴容後的大小為最接近當前size的二次冪。

在擴容之後，會進行元素遷移，從舊hashmap遷移到新hashmap。

為什麼擴容後的大小要是二次冪？

1）在遷移的時候，會根據key重新計算hashcode，重新獲取新的index。此時如果最大容量每次都是2的二次冪，那麼在計算index的時候（預設情況下），有50%的概率其位置不發生改變，可以與原數組保持一致。

2）同時，如果最大長度保持為二次冪，那麼散列的會更均勻，如果不是二次冪，會導致某些位置永遠不會被散列到，浪費地址空間。

3.關於重寫equals必須要重寫hashcode的辨析。

作者通過get_entry方法引出的這個問題，但是我覺得並不很合適，原因如下：

首先我們看代碼：

final Entry<K,V> getEntry(Object key) {
            
        if (size == 0) {
            return null;
        }
        //通過key的hashcode值計算hash值
        int hash = (key == null) ? 0 : hash(key);
        //indexFor (hash&length-1) 獲取最終數組索引，然後遍歷鏈表，通過equals方法比對找出對應記錄
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && 
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }    

通過代碼可以看到，在獲取元素的時候，首先是根據key計算hashcode，然後根據hashcode找到index，之後進行兩個判斷

1）hashcode是否相等

2）key是否equal

作者提到，這裡有些人會認為再次判斷hashcode是否相等多此一舉，僅通過equals即可，這是不對的。但是作者後面又說這和重寫equals沒重寫hashcode相關，因為只重寫equals不重寫hashcode，那麼equals可能相等，但是hashcode不等，此時按照Object的HashCode約定，不能返回元素。

我認為這裡說的是對的，但是不夠清晰。為了講清楚，我們把其分為兩中情況。

1）hashcode和equals都不重寫，此時二者比較的都是key的地址（如果key是對象）

此時對於某一次get，可以得到一個hashcode，通過hashcode，得到index，然後進行判斷

1】hashcode是否相等

2】key是否equal

此時，如果捨棄判斷1】，我們會發現，因為此時equals和hashcode等價，捨棄其中任何一個都不會違背Object的HashCode約定。

2)重寫equals，不重寫hashcode

此時對於某一次get，可以得到一個hashcode，通過hashcode，得到index，然後進行判斷

1】hashcode是否相等

2】key是否equal

此時，如果捨棄判斷1】，我們會發現，因為此時equals和hashcode不等價，同時因為index是由hashcode計算出來的，不同的hashcode可能得到同樣的index，沒有判斷1】，得到的返回值的hashcode不一定等，但是因為內容相同，可以得到返回值，此時得到的返回值是不符合Object的HashCode約定，該約定要求hashcode的範圍一定要比equals大。

4.關於為什麼重寫equals必須要重寫hashcode

如果不重寫，我們會發現，在hashmap的主幹（數組）上的key-value對key可能相等，但是因為hashcode不等，得到的index也不等，因為計算hashcode用的是地址，不是值。按照要求，此時應該出現hash衝突。這也導致key正確，但是定位不到正確的位置，得到正確的值，得到null。

【講得不好，後續接著改】

5. JDK1.8中HashMap的性能優化

鏈表>=8，數組長>=64，鏈表變紅黑樹。