深入理解hashCode和hash演算法（面試官都饞哭了）-有解無憂

本人當初剛接觸java的時候一說到hash演算法或者hashCode也是蛋蛋疼，兩只都疼

后來由于面試，花了整整一天時間來研究hash，搞懂后發現其實也不難理解，時隔一年突然想起來，寫篇博客記錄下；

以前我莫得選擇，現在我想搞懂hash，搞懂演算法，做大做強，再創輝煌！

本文會圍繞以下幾個點來講：

什么是hashCode？為什么說java離不開hashCode？
hashCode和equals的關系
剖析hashMap的hash演算法

為什么會有hashCode
先拋一個結論

hashCode的設計初衷是提高哈希容器的性能

拋開hashCode，現在讓你對比兩個物件是否相等，你會怎么做？

thisObj == thatObj
thisObj.equals(thatObj)

我想不出第三種了，而且這兩種其實沒啥大的區別，object的equals()方法底層也是==，jdk1.8 Object類的第148行；

    public boolean equals(Object obj) {
        return (this == obj);
    }

為什么有了equals還要有hashCode，既生瑜何生亮？？上面說了，hashCode的設計初衷是提高哈希容器的性能，equals的效率是比hashCode高的，不信的可以自己去試一下；

像我們常用的HashMap、HashTable等，理論上講是可以不要hashCode的，但是會犧牲很多性能，這肯定不是我們想看到的，互聯網時代，比的就是誰更快；

所以為什么說java離不開hashCode，答案就是為了提高hash容器性能；

什么是hashCode
知道hashCode存在的意義后，我們來研究下hashCode，看下長什么樣

物件呼叫hashCode方法后，會回傳一串int型別的數字碼

        BloomFilterTest bloomFilter = new BloomFilterTest();
        log.info("物件的hashcode：{}", bloomFilter.hashCode());

        log.info("1433223的hashcode：{}", "1433223".hashCode());
        log.info("郭德綱的hashcode：{}", "郭德綱".hashCode());
        log.info("小郭德綱的hashcode：{}", "小郭德綱".hashCode());
        log.info("彭于晏的hashcode：{}", "彭于晏".hashCode());
        log.info("唱跳rap籃球的hashcode：{}", "唱跳rap籃球".hashCode());

運行結果

物件的hashcode：459296537
1433223的hashcode：2075391824
郭德綱的hashcode：36446088
小郭德綱的hashcode：738530585
彭于晏的hashcode：24125870
唱跳rap籃球的hashcode：-767899628 ##因為回傳值是int型別，有負數很正常

可以看出，物件的hashcode值跟物件本身的值沒啥聯系，比如郭德綱和小郭德綱，雖然只差一個字，它們的hashCode值不能說一模一樣，也可以說是毫不相干，嚶嚶嚶~

hashCode和equals的關系

java規定：

如果兩個物件的hashCode()相等，那么他們的equals()不一定相等，
如果兩個物件的equals()相等，那么他們的hashCode()必定相等，

還有一點，重寫equals()方法時候一定要重寫hashCode()方法，不要問為什么，無腦寫就行了，會省很多事

hash演算法

前面都是鋪墊，這才是今天的主題

我們以HashMap的hash演算法來看，個人認為這是很值得搞懂的hash演算法，設計超級超級巧妙

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

這是hashMap的hash演算法，我們一步一步來看

(h = key.hashCode()) ^ (h >>> 16)

hashCode就hashCode嘛，為啥還要>>>16，這個 ^ 又是啥，不著急一個一個來說

hashMap我們知道默認初始容量是16，也就是有16個桶，那hashmap是通過什么來計算出put物件的時候該放到哪個桶呢

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

上面是hashmap的getNode方法，對hashmap原始碼有興趣的同學自行研究，我們今天主要看這一句：(n - 1) & hash

也就是說hashmap是通過陣列長度-1&key的hash值來計算出陣列下標的，這里的hash值就是上面(h = key.hashCode()) ^ (h >>> 16)計算出來的值

不要慌不要慌不要慌，看不懂沒關系，我們現在總結下目前的疑問

為什么陣列長度要 - 1，直接陣列長度&key.hashCode不行嗎
為什么要length-1 & key.hashCode計算下標，而不是用key.hashCode % length
為什么要^運算
為什么要>>>16

先說結論

陣列長度-1、^運算、>>>16，這三個操作都是為了讓key在hashmap的桶中盡可能分散
用&而不用%是為了提高計算性能

我們先看下如果陣列長度不-1和不進行>>>16運算造成的結果，知道了結果我們后面才來說為什么，這樣子更好理解

log.info("陣列長度不-1：{}", 16 & "郭德綱".hashCode());
log.info("陣列長度不-1：{}", 16 & "彭于晏".hashCode());
log.info("陣列長度不-1：{}", 16 & "李小龍".hashCode());
log.info("陣列長度不-1：{}", 16 & "蔡徐雞".hashCode());
log.info("陣列長度不-1：{}", 16 & "唱跳rap籃球雞叫".hashCode());

log.info("陣列長度-1但是不進行異或和>>>16運算：{}", 15 & "郭德綱".hashCode());
log.info("陣列長度-1但是不進行異或和>>>16運算：{}", 15 & "彭于晏".hashCode());
log.info("陣列長度-1但是不進行異或和>>>16運算：{}", 15 & "李小龍".hashCode());
log.info("陣列長度-1但是不進行異或和>>>16運算：{}", 15 & "蔡徐雞".hashCode());
log.info("陣列長度-1但是不進行異或和>>>16運算：{}", 15 & "唱跳rap籃球雞叫".hashCode());

log.info("陣列長度-1并且進行異或和>>>16運算：{}", 15 & ("郭德綱".hashCode()^("郭德綱".hashCode()>>>16)));
log.info("陣列長度-1并且進行異或和>>>16運算：{}", 15 & ("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));
log.info("陣列長度-1并且進行異或和>>>16運算：{}", 15 & ("李小龍".hashCode()^("李小龍".hashCode()>>>16)));
log.info("陣列長度-1并且進行異或和>>>16運算：{}", 15 & ("蔡徐雞".hashCode()^("蔡徐雞".hashCode()>>>16)));
log.info("陣列長度-1并且進行異或和>>>16運算：{}", 15 & ("唱跳rap籃球雞叫".hashCode()^("唱跳rap籃球雞叫".hashCode()>>>16)));

陣列長度不-1：0
陣列長度不-1：0
陣列長度不-1：16
陣列長度不-1：16
陣列長度不-1：16
陣列長度-1但是不進行異或和>>>16運算：8
陣列長度-1但是不進行異或和>>>16運算：14
陣列長度-1但是不進行異或和>>>16運算：8
陣列長度-1但是不進行異或和>>>16運算：2
陣列長度-1但是不進行異或和>>>16運算：14
陣列長度-1并且進行異或和>>>16運算：4
陣列長度-1并且進行異或和>>>16運算：14
陣列長度-1并且進行異或和>>>16運算：7
陣列長度-1并且進行異或和>>>16運算：13
陣列長度-1并且進行異或和>>>16運算：2

一下就看出區別了哇，第一組回傳的下標就只有0和16，第二組也只有2、8、14，第三組的下標就很分散，這才是我們想要的

這結合hashMap來看，前兩組造成的影響就是key幾乎全部懟到同一個桶里，及其不分散，用行話講就是有太多的hash沖突，這對hashMap的性能有很大影響，hash沖突造成的鏈表紅黑樹轉換那些具體的原因這里就不展開說了

原理
知道了結果，現在說說其中的玄學

1、為什么陣列長度要 - 1，直接陣列長度&key.hashCode不行嗎

hashMap默認長度是16，看看16的二進制碼是多少

log.info("16的二進制碼：{}",Integer.toBinaryString(16));  
//16的二進制碼：10000，

再看看key.hashCode()的二進制碼是多少，以郭德綱為例

log.info("key的二進制碼：{}",Integer.toBinaryString("郭德綱".hashCode()));
//key的二進制碼：10001011000001111110001000

length & key.hashCode()  => 10000 & 10001011000001111110001000
位數不夠，高位補0，即

0000 0000 0000 0000 0000 0001 0000 
                & 
0010 0010 1100 0001 1111 1000 1000

&運算規則是第一個運算元的的第n位于第二個運算元的第n位都為1才為1，否則為0
所以結果為0000 0000 0000 0000 0000 0000 0000，即 0

在這里插入圖片描述

冷靜分析，問題就出在16的二進制碼上，它碼是10000，只有遇到hash值二進制碼倒數第五位為1的key他們&運算的結果才不等于0，這句話好好理解下，看不懂就別強制看，去摸會兒魚再回來看

再來看16-1的二進制碼，它碼是1111，同樣用郭德綱這個key來舉例

(length-1) & key.hashCode()  => 1111 & 10001011000001111110001000
位數不夠，高位補0，即

0000 0000 0000 0000 0000 0000 1111 
                & 
0010 0010 1100 0001 1111 1000 1000

&運算規則是第一個運算元的的第n位于第二個運算元的第n位都為1才為1，否則為0
所以結果為0000 0000 0000 0000 0000 0000 1000，即 8

如果還看不出這其中的玄機，你就多搞幾個key來試試，總之記住，限制它們&運算的結果就會有很多種可能性了，不再受到hash值二進制碼倒數第五位為1才能為1的限制

2、為什么要length-1&key.hashCode計算下標，而不是用key.hashCode%length

這個其實衍生出三個知識點

1、其實(length-1)&key.hashCode計算出來的值和key.hashCode%length是一樣的

log.info("(length-1)&key.hashCode：{}",15&"郭德綱".hashCode());
log.info("key.hashCode%length：{}","郭德綱".hashCode()%16);

//  (length-1)&key.hashCode：8
//  key.hashCode%length：8

那你可能更蒙逼了，都一樣的為啥不用%，這就要說到第二個知識點

2、只有當length為2的n次方時，(length-1)&key.hashCode才等于key.hashCode%length，比如當length為15時

log.info("(length-1)&key的hash值：{}",14&"郭德綱".hashCode());
log.info("key的hash值%length：{}","郭德綱".hashCode()%15);

//  (length-1)&key.hashCode：8
//  key.hashCode%length：3

可能又有小朋友會思考，我不管那我就想用%運算，要用魔法打敗魔法，請看第三點

3、用&而不用%是為了提高計算性能，對于處理器來講，&運算的效率是高于%運算的，就這么簡單，除此之外，除法的效率也沒&高

3、為什么要進行^運算

這是異或運算子，第一個運算元的的第n位于第二個運算元的第n位相反才為1，否則為0
我們多算幾個key的值出來對比

//不進行異或運算回傳的陣列下標
log.info("郭德綱：{}", Integer.toBinaryString("郭德綱".hashCode()));            
log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()));            
log.info("李小龍：{}", Integer.toBinaryString("李小龍".hashCode()));            
log.info("蔡徐雞：{}", Integer.toBinaryString("蔡徐雞".hashCode()));            
log.info("唱跳rap籃球雞叫：{}", Integer.toBinaryString("唱跳rap籃球雞叫".hashCode()));

00001000101100000111111000 1000
00000101110000001000011010 1110
00000110001111100100010011 1000
00000111111111111100010111 0010
10111010111100100011001111 1110

進行&運算，看下它們回傳的陣列下標，length為16的話，只看后四位即可
8
14
8
2
14

//進行異或運算回傳的陣列下標
log.info("郭德綱：{}", Integer.toBinaryString("郭德綱".hashCode()^("郭德綱".hashCode()>>>16)));                  
log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));                  
log.info("李小龍：{}", Integer.toBinaryString("李小龍".hashCode()^("李小龍".hashCode()>>>16)));                  
log.info("蔡徐雞：{}", Integer.toBinaryString("蔡徐雞".hashCode()^("蔡徐雞".hashCode()>>>16)));                  
log.info("唱跳rap籃球雞叫：{}", Integer.toBinaryString("唱跳rap籃球雞叫".hashCode()^("唱跳rap籃球雞叫".hashCode()>>>16)));

0000001000101100000111011010 0100
0000000101110000001000001101 1110
0000000110001111100100001011 0111
0000000111111111111100001000 1101
0010111010111100101000100100 0010

進行&運算，看下它們回傳的陣列下標，length為16的話，只看后四位即可
4
14
7
13
2

很明顯，做了^運算的陣列下標更分散

4、為什么要>>>16

這是無符號右移16位，位數不夠，高位補0
其實>>>16和^運算是相輔相成的關系，目的都是為了讓陣列下標更分散，看一看>>>16的效果就知道了
（單獨看<<<16可能看不出啥效果，但搭配上^就很容易看出來了，總之，記住這是為了讓陣列下標更加分散的騷操作）

log.info("郭德綱：{}", Integer.toBinaryString("郭德綱".hashCode()));  
log.info("郭德綱>>>16：{}", Integer.toBinaryString("郭德綱".hashCode()>>>16)); 
0000 0010 0010 1100 0001 1111 1000 1000
0000 0000 0000 0000 0000 0010 0010 1100

log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()));  
log.info("彭于晏>>>16：{}", Integer.toBinaryString("彭于晏".hashCode()>>>16)); 
0000 0001 0111 0000 0010 0001 1010 1110
0000 0000 0000 0000 0000 0001 0111 0000

log.info("李小龍：{}", Integer.toBinaryString("李小龍".hashCode()));    
log.info("李小龍>>>16：{}", Integer.toBinaryString("李小龍".hashCode()>>>16)); 
0000 0001 1000 1111 1001 0001 0011 1000
0000 0000 0000 0000 0000 0001 1000 1111

log.info("蔡徐雞：{}", Integer.toBinaryString("蔡徐雞".hashCode()));  
log.info("蔡徐雞>>>16：{}", Integer.toBinaryString("蔡徐雞".hashCode()>>>16));
0000 0001 1111 1111 1111 0001 0111 0010
0000 0000 0000 0000 0000 0001 1111 1111

log.info("唱跳rap籃球雞叫：{}", Integer.toBinaryString("唱跳rap籃球雞叫".hashCode()));          
log.info("唱跳rap籃球雞叫>>>16：{}", Integer.toBinaryString("唱跳rap籃球雞叫".hashCode()>>>16));                                                                           
0010 1110 1011 1100 1000 1100 1111 1110
0000 0000 0000 0000 0010 1110 1011 1100

搞java你是避不開hash家族的，與其逃避，不如花點心思徹底搞懂！

嚶嚶嚶~ 寫了整整一天終于我寫完了

嚶嚶嚶~ 好害羞

嚶嚶嚶~ 好緊張

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/254534.html

標籤：java

上一篇：Java中遍歷Map集合的五種方式

下一篇：【每日藍橋】16、一三年省賽Java組真題“幸運數”