Hash沖突是怎么回事

Hash沖突是怎么回事

在這個文章正式開始之前，先幾句話把這個問題說清楚了：我們常說的 Hash 沖突到底是怎么回事？

直接上個圖片：

 

你說你看到這個圖片的時候想到了什么東西？

有沒有想到 HashMap 的數(shù)組加鏈表的結構？

對咯，我這里就是以 HashMap 為切入點，給大家講一下 Hash 沖突。

接著我們看下面這張圖：

 

假設現(xiàn)在我們有個值為 [why技術] 的 key，經過 Hash 算法后，計算出值為 1，那么含義就是這個值應該放到數(shù)組下標為 1 的地方。

但是如圖所示，下標為 1 的地方已經掛了一個 eat 的值了。這個坑位已經被人占著了。

那么此時此刻，我們就把這種現(xiàn)象叫為 Hash 沖突。

HashMap 是怎么解決 Hash 沖突的呢？

鏈地址法，也叫做拉鏈法。

數(shù)組中出現(xiàn) Hash 沖突了，這個時候鏈表的數(shù)據(jù)結構就派上用場了。

鏈表怎么用的呢？看圖：

 

這樣問題就被我們解決了。

其實 hash 沖突也就是這么一回事：不同的對象經過同一個 Hash 算法后得到了一樣的 HashCode。

那么寫到這里的時候我突然想到了一個面試題：

請問我上面的圖是基于 JDK 什么版本的 HashMap 畫的圖？

為什么想到了這個面試題呢？

因為我畫圖的時候猶豫了大概 0.3 秒，往鏈表上掛的時候，我到底是使用頭插法還是尾插法呢？

 

眾所周知，JDK 7 中的 HashMap 是采用頭插法的，即 [why技術] 在 [eat] 之前，JDK 8 中的 HashMap 采用的是尾插法。

這面試題怎么說呢，真的無聊。但是能怎么辦呢，八股文該背還是得背。

面試嘛，背一背，不寒磣。

構建 HashCode 一樣的 String

前面我們知道了，Hash 沖突的根本原因是不同的對象經過同一個 Hash 算法后得到了一樣的 HashCode。

這句話乍一聽：嗯，很有道理，就是這么一回事，沒有問題。

比如我們常用的 HashMap ，絕大部分情況 key 都是 String 類型的。要出現(xiàn) Hash 沖突，最少需要兩個 HashCode 一樣的 String 類。

那么我問你：怎么才能快速弄兩個 HashCode 一樣的 String 呢？

 

怎么樣，有點懵逼了吧？

從很有道理，到有點懵逼只需要一個問題。

來，我?guī)惴治鲆徊ā?/p>

我先問你：長度為 1 的兩個不一樣的 String，比如下面這樣的代碼，會不會有一樣的 HashCode？

String a = "a";
String b = "b";

肯定是不會的，對吧。

如果你不知道的話，建議你去 ASCII 碼里面找答案。

我們接著往下梳理，看看長度為 2 的 String 會不會出現(xiàn)一樣的 HashCode？

要回答這個問題，我們要先看看 String 的 hashCode 計算方法，我這里以 JDK 8 為例：

 

我們假設這兩個長度為 2 的 String，分別是 xy 和 ab 吧。

注意這里的 xy 和 ab 都是占位符，不是字符串。

類似于小學課本中一元二次方程中的未知數(shù) x 和 y，我們需要帶入到上面的 hashCode 方法中去計算。

hashCode 算法，最主要的就是其中的這個 for 循環(huán)。

 

for 循環(huán)里面的有三個我們不知道是啥的東西：h，value.length 和 val[i]。我們 debug 看一下：

 

h 初始情況下等于 0。

String 類型的底層結構是 char 數(shù)組，這個應該知道吧。

所以，value.length 是字符串的長度。val[] 就是這個 char 數(shù)組。

把 xy 帶入到 for 循環(huán)中，這個 for 循環(huán)會循環(huán) 2 次。

第一次循環(huán)：h=0，val[0]=x，所以 h=31*0+x，即 h=x。

第二次循環(huán)：h=x，val[1]=y，所以 h=31*x+y。

所以，經過計算后， xy 的 hashCode 為 31*x+y。

同理可得，ab 的 hashCode 為 31*a+b。

由于我們想要構建 hashCode 一樣的字符串，所以可以得到等式：

31x+y=31a+b

那么問題就來了：請問 x，y，a，b 分別是多少？

你算的出來嗎？

你算的出來個錘子！黑板上的排列組合你不是舍不得解開，你就是解不開。

但是我可以解開，帶大家看看這個題怎么搞。

數(shù)學課開始了。注意，我要變形了。

 

31x+y=31a+b 可以變形為：

31x-31a=b-y。

即，31(x-a)=b-y。

這個時候就清晰很多了，很明顯，上面的等式有一個特殊解：

x-a=1，b-y=31。

因為，由上可得：對于任意兩個字符串 xy 和 ab，如果它們滿足 x-a=1，即第一個字符的 ASCII 碼值相差為 1，同時滿足 b-y=31，即第二個字符的 ASCII 碼值相差為 -31。那么這兩個字符的 hashCode 一定相等。

都已經說的這么清楚了，這樣的組合對照著 ASCII 碼表來找，不是一抓一大把嗎？

Aa 和 BB，對不對？

Ab 和 BC，是不是？

Ac 和 BD，有沒有？

 

好的?，F(xiàn)在，我們可以生成兩個 HashCode 一樣的字符串了。

我們在稍微加深一點點難度。假設我要構建 2 個以上 HashCode 一樣的字符串該怎么辦？

我們先分析一下。

Aa 和 BB 的 HashCode 是一樣的。我們把它兩一排列組合，那不還是一樣的嗎？

比如這樣的：AaBB，BBAa。

 

再比如我之前《震驚！ConcurrentHashMap里面也有死循環(huán)？》這篇文章中出現(xiàn)過的例子，AaAa，BBBB：

你看，神奇的事情就出現(xiàn)了。

我們有了 4 個 hashCode 一樣的字符串了。

 

有了這 4 個字符串，我們再去和  Aa，BB 進行組合，比如 AaBBAa，BBAaBB......

4*2=8 種組合方式，我們又能得到 8 個 hashCode 一樣的字符串了。

 

等等，我好像發(fā)現(xiàn)了什么規(guī)律似的。

如果我們以 Aa，BB 為種子數(shù)據(jù)，經過多次排列組合，可以得到任意個數(shù)的 hashCode 一樣的字符串。字符串的長度隨著個數(shù)增加而增加。

文字我還說不太清楚，直接 show you code 吧，如下：

public class CreateHashCodeSomeUtil {

    /**
     * 種子數(shù)據(jù)：兩個長度為 2 的 hashCode 一樣的字符串
     */
    private static String[] SEED = new String[]{"Aa", "BB"};
    
    /**
     * 生成 2 的 n 次方個 HashCode 一樣的字符串的集合
     */
    public static List<String> hashCodeSomeList(int n) {
        List<String> initList = new ArrayList<String>(Arrays.asList(SEED));
        for (int i = 1; i < n; i++) {
            initList = createByList(initList);
        }
        return initList;
    }

    public static List<String> createByList(List<String> list) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < SEED.length; ++i) {
            for (String str : list) {
                result.add(SEED[i] + str);
            }
        }
        return result;
    }
}

通過上面的代碼，我們就可以生成任意多個 hashCode 一樣的字符串了。

就像這樣：

 

所以，別再問出這樣的問題了：

 

 

有了這些 hashCode 一樣的字符串，我們把這些字符串都放到HashMap 中，代碼如下：

public class HashMapTest {
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("Aa", "Aa");
        hashMap.put("BB", "BB");
        hashMap.put("AaAa", "AaAa");
        hashMap.put("AaBB", "AaBB");
        hashMap.put("BBAa", "BBAa");
        hashMap.put("BBBB", "BBBB");
        hashMap.put("AaAaAa", "AaAaAa");
        hashMap.put("AaAaBB", "AaAaBB");
        hashMap.put("AaBBAa", "AaBBAa");
        hashMap.put("AaBBBB", "AaBBBB");
        hashMap.put("BBAaAa", "BBAaAa");
        hashMap.put("BBAaBB", "BBAaBB");
        hashMap.put("BBBBAa", "BBBBAa");
        hashMap.put("BBBBBB", "BBBBBB");
    }
}

最后這個 HashMap 的長度會經過兩次擴容。擴容之后數(shù)組長度為 64：

 

但是里面只被占用了三個位置，分別是下標為 0,31,32 的地方：

 

 

 

畫圖如下：

 

看到了吧，刺不刺激，長度為 64 的數(shù)組，存 14 個數(shù)據(jù)，只占用了 3 個位置。

這空間利用率，也太低了吧。

所以，這樣就算是 hack 了 HashMap。恭喜你，掌握了一項黑客攻擊技術：hash 沖突 Dos 。

如果你想了解的更多?？梢钥纯词^哥的這篇文章：《沒想到 Hash 沖突還能這么玩，你的服務中招了嗎？》。

看到上面的圖，不知道大家有沒有覺得有什么不對勁的地方？

如果沒有，那么我再給你提示一下：數(shù)組下標為 32 的位置下，掛了一個長度為 8 的鏈表。

是不是，恍然大悟了。在 JDK 8 中，鏈表轉樹的閾值是多少？

 

所以，在當前的案例中，數(shù)組下標為 32 的位置下掛的不應該是一個鏈表，而是一顆紅黑樹。

對不對？

 

對個錘子對！有的人稍不留神就被帶偏了

 

這是不對的。鏈表轉紅黑樹的閾值是節(jié)點大于 8 個，而不是等于 8 的時候。

也就是說需要再來一個經過 hash 計算后，下標為 32 的、且 value 和之前的 value 都不一樣的 key 的時候，才會觸發(fā)樹化操作。

不信，我給你看看現(xiàn)在是一個什么節(jié)點：

 

沒有騙你吧？從上面的圖片可以清楚的看到，第 8 個節(jié)點還是一個普通的 node。

而如果是樹化節(jié)點，它應該是長這樣的：

 

不信，我們再多搞一個 hash 沖突進來，帶你親眼看一下，代碼是不會騙人的。

那么怎么多搞一個沖突出來呢？

最簡單的，這樣寫：

 

這樣沖突不就多一個了嗎？我真是一個天才，情不自禁的給自己鼓起掌來。

好了，我們看一下現(xiàn)在的節(jié)點狀態(tài)是怎么樣的：

怎么樣，是不是變成了 TreeNode ，沒有騙你吧？

 

什么？你問我為什么不把圖畫出來？

別問，問就是我不會畫紅黑樹。正經人誰畫那玩意。

另外，我還想多說一句，關于一個 HashMap 的面試題的一個坑。

面試官問：JDK 8 的 HashMap 鏈表轉紅黑樹的條件是什么？

絕大部分背過面試八股文的朋友肯定能答上來：當鏈表長度大于 8 的時候。

這個回答正確嗎？

是正確的，但是只正確了一半。

還有一個條件是數(shù)組長度大于 64 的時候才會轉紅黑樹。

源碼里面寫的很清楚，數(shù)組長度小于 64，直接擴容，而不是轉紅黑樹：

 

感覺很多人都忽略了“數(shù)組長度大于 64 ”這個條件。

背八股文，還是得背全了。

比如下面這種測試用例：

 

它們都會落到數(shù)組下標為 0 的位置上。

當?shù)?9 個元素 BBBBAa 落進來的時候，會走到 treeifyBin 方法中去，但是不會觸發(fā)樹化操作，只會進行擴容操作。

因為當前長度為默認長度，即 16。不滿足轉紅黑樹條件。

所以，從下面的截圖，我們可以看到，標號為 ① 的地方，數(shù)組長度變成了 32，鏈表長度變成了  9 ，但是節(jié)點還是普通 node：

 

怎么樣，有點意思吧，我覺得這樣學 HashMap 有趣多了。

 

實體類當做 key

上面的示例中，我們用的是 String 類型當做 HashMap 中的 key。

這個場景能覆蓋我們開發(fā)場景中的百分之 95 了。

但是偶爾會有那么幾次，可能會把實體類當做 key 放到 HashMap 中去。

注意啊，面試題又來了：在 HashMap 中可以用實體類當對象嗎？

那必須的是可以的啊。但是有坑，注意別踩進去了。

我拿前段時間看到的一個新聞給大家舉個例子吧：

 

假設我要收集學生的家庭信息，用 HashMap 存起來。

那么我的 key 是學生對象， value 是學生家庭信息對象。

他們分別是這樣的：

public class HomeInfo {

    private String homeAddr;
    private String carName;
     //省略改造方法和toString方法
}

public class Student {

    private String name;
    private Integer age;
     //省略改造方法和toString方法

}

然后我們的測試用例如下：

public class HashMapTest {

    private static Map<Student, HomeInfo> hashMap = new HashMap<Student, HomeInfo>();

    static {
        Student student = new Student("why", 7);
        HomeInfo homeInfo = new HomeInfo("大南街", "自行車");
        hashMap.put(student, homeInfo);
    }

    public static void main(String[] args) {
        updateInfo("why", 7, "濱江路", "摩托");
        for (Map.Entry<Student, HomeInfo> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey()+"-"+entry.getValue());
        }
    }

    private static void updateInfo(String name, Integer age, String homeAddr, String carName) {
        Student student = new Student(name, age);
        HomeInfo homeInfo = hashMap.get(student);
        if (homeInfo == null) {
            hashMap.put(student, new HomeInfo(homeAddr, carName));
        }
    }
}

初始狀態(tài)下，HashMap 中已經有一個名叫 why 的 7 歲小朋友了，他家住大南街，家里的交通工具是自行車。

然后，有一天他告訴老師，他搬家了，搬到了濱江路去，而且家里的自行車換成了摩托車。

于是老師就通過頁面，修改了 why 小朋友的家庭信息。

最后調用到了 updateInfo 方法。

嘿，你猜怎么著？

我?guī)憧匆幌螺敵觯?/p>

 

更新完了之后，他們班上出現(xiàn)了兩個叫 why 的 7 歲小朋友了，一個住在大南街，一個住在濱江路。

更新變新增了，你說神奇不神奇？

現(xiàn)象出來了，那么根據(jù)現(xiàn)象定位問題代碼不是手到擒來的事兒？

很明顯，問題就出在這個地方：

 

這里取出來的 homeInfo 為空了，所以才會新放一個數(shù)據(jù)進去。

那么我們看看為啥這里為空。

跟著 hashMap.get() 源碼進去瞅一眼：

 

標號為 ① 的地方是計算 key ，也就是 student 對象的 hashCode。而我們 student 對象并沒有重寫 hashCode，所以調用的是默認的 hashCode 方法。

這里的 student 是 new 出來的：

 

所以，這個 student 的 hashCode 勢必和之前在 HashMap 里面的 student 不是一樣的。

因此，標號為 ③ 的地方，經過 hash 計算后得出的 tab 數(shù)組下標，對應的位置為 null。不會進入 if 判斷，這里返回為 null。

那么解決方案也就呼之欲出了：重寫對象的 hashCode 方法即可。

是嗎？

等等，你回來，別拿著半截就跑。我話還沒說完呢。

接著看源碼：

 

HashMap put 方法執(zhí)行的時候，用的是 equals方法判斷當前 key 是否與表中存在的 key 相同。

我們這里沒有重寫 equals方法，因此這里返回了 false。

所以，如果我們 hashCode 和 equals方法都沒有重寫，那么就會出現(xiàn)下面示意圖的情況：

 

如果，我們重寫了 hashCode，沒有重寫 equals 方法，那么就會出現(xiàn)下面示意圖的情況：

 

總之一句話：在 HashMap 中，如果用對象做 key，那么一定要重寫對象的 hashCode 方法和 equals方法。否則，不僅不能達到預期的效果，而且有可能導致內存溢出。

比如上面的示例，我們放到循環(huán)中去，啟動參數(shù)我們加上 -Xmx10m，運行結果如下：

 

因為每一次都是 new 出來的 student 對象，hashCode 都不盡相同，所以會不停的觸發(fā)擴容的操作，最終在 resize 的方法拋出了 OOM 異常。

奇怪的知識又增加了

奇怪的知識又增加了兩個。

第一個是在這本書里面，對于 HashMap 里面放對象的示例是這樣的：

 

Groundhog：土撥鼠、旱獺。

Prediction：預言、預測、預告。

考慮一個天氣預報系統(tǒng)，將土撥鼠和預報聯(lián)系起來。

這 TM 是個什么讀不懂的神仙需求？

 

幸好 why 哥學識淵博，閉上眼睛，去我的知識倉庫里面搜索了一番。

原來是這么一回事。

在美國的賓西法尼亞州，每年的 2 月 2 日，是土撥鼠日。

根據(jù)民間的說法，如果土撥鼠在 2 月 2 號出洞時見到自己的影子，然后這個小東西就會回到洞里繼續(xù)冬眠，表示春天還要六個星期才會到來。如果見不到影子，它就會出來覓食或者求偶，表示寒冬即將結束。

這就呼應上了，通過判斷土撥鼠出洞的時候是否能看到影子，從而判斷冬天是否結束。

這樣，需求就說的通了。

 

第二個奇怪的知識是這樣的。

關于 HashCode 方法，《Java編程思想(第4版)》里面是這樣寫的：

我一眼就發(fā)現(xiàn)了不對勁的地方：result=37*result+c。

前面我們才說了，基數(shù)應該是 31 才對呀？

 

作者說這個公式是從《Effective Java（第1版）》的書里面拿過來的。

這兩本書都是 java 圣經啊，建議大家把夢幻聯(lián)動打在留言區(qū)上。

《Effective Java（第1版）》太久遠了，我這里只有第 2 版和第 3 版的實體書。

于是我在網上找了一圈第 1 版的電子書，終于找到了對應描述的地方：

 

可以看到，書里給出的公式確實是基于 37 去計算的。

翻了一下第三版，一樣的地方，給出的公式是這樣的：

 

而且，你去網上搜：String 的 hashCode 的計算方法。

都是在爭論為什么是 31 。很少有人提到 37 這個數(shù)。

其實，我猜測，在早期的 JDK 版本中 String 的 hashCode 方法應該用的是 37 ，后來改為了 31 。

我想去下載最早的 JDK 版本去驗證一下的，但是網上翻了個底朝天，沒有找到合適的。

書里面為什么從 37 改到 31 呢？

作者是這樣解釋的，上面是第 1 版，下面是第 2 版：

用方框框起來的部分想要表達的東西是一模一樣的，只是對象從 37 變成了 31 。

而為什么從 37 變成 31 ，作者在第二版里面解釋了，也就是我用下劃線標注的部分。

31 有個很好的特許，即用位移和減法來代替乘法，可以得到更好的性能：

31*i==（i<<5）-i。現(xiàn)代的虛擬機可以自動完成這種優(yōu)化。

從 37 變成 31，一個簡單的數(shù)字變化，就能帶來性能的提升。

個中奧秘，很有意思，有興趣的可以去查閱一下相關資料。

真是神奇的計算機世界。