面試官:換人!他連哈希扣的都不懂

前言

相信你面試的時候,肯定被問過 hashCode 和 equals 相關的問題 。如:

  • hashCode 是什么?它是怎么得來的?有什么用?
  • 經典題,equals 和 == 有什么區別?
  • 為什么要重寫 equals 和 hashCode ?
  • 重寫了 equals ,就必須要重寫 hashCode 嗎?為什么?
  • hashCode 相等時,equals 一定相等嗎?反過來呢?

好的,上面就是靈魂拷問環節。其實,這些問題仔細想一下也不難,主要是平時我們很少去思考它。

正文

下面就按照上邊的問題順序,一個一個剖析它。扒開 hashCode 的神秘面紗。

什么是 hashCode?

我們通常說的 hashCode 其實就是一個經過哈希運算之后的整型值。而這個哈希運算的算法,在 Object 類中就是通過一個本地方法 hashCode() 來實現的(HashMap 中還會有一些其它的運算)。

public native int hashCode();

可以看到它是一個本地方法。那么,想要了解這個方法到底是用來干嘛的,最直接有效的方法就是,去看它的源碼注釋。

下邊我就用我蹩腳的英文翻譯一下它的意思。。。

返回當前對象的一個哈希值。這個方法用于支持一些哈希表,例如 HashMap 。

通常來講,它有如下一些約定:

  • 若對象的信息沒有被修改,那么,在一個程序的執行期間,對于相同的對象,不管調用多少次 hashCode 方法,都應該返回相同的值。當然,在相同程序的不同執行期間,不需要保持結果一致。
  • 若兩個對象的 equals 方法返回值相同,那么,調用它們各自的 hashCode 方法時,也必須返回相同的結果。(ps: 這句話解答了上邊的一些問題,后面會用例子來證明這一點)
  • 當兩個對象的 equals 方法返回值不同時,那么它們的 hashCode 方法不用保證必須返回不同的值。但是,我們應該知道,在這種情況下,我們最好也設計成 hashCode 返回不同的值。因為,這樣做有助于提高哈希表的性能。

在實際情況下,Object 類的 hashCode 方法在不同的對象中確實返回了不同的哈希值。這通常是通過把對象的內部地址轉換為一個整數來實現的。

ps: 這里說的內部地址就是指物理地址,也就是內存地址。需要注意的是,雖然 hashCode 值是依據它的內存地址而得來的。但是,不能說 hashCode 就代表對象的內存地址,實際上,hashCode 地址是存放在哈希表中的。

上邊的源碼注釋真可謂是句句珠璣,把 hashCode 方法解釋的淋漓盡致。一會兒我通過一個案例說明,就能明白我為什么這樣說了。

什么是哈希表?

上文中提到了哈希表。什么是哈希表呢?我們直接看百度百科的解釋。

用一張圖來表示它們的關系。

左邊一列就是一些關鍵碼(key),通過哈希函數,它們都會得到一個固定的值,分別對應右邊一列的某個值。右邊的這一列就可以認為是一張哈希表。

而且,我們會發現,有可能有些 key 不同,但是它們對應的哈希值卻是一樣的,例如 aa,bb 都指向 1001 。但是,一定不會出現同一個 key 指向不同的值。

這也非常好理解,因為哈希表就是用來查找 key 的哈希地址的。在 key 確定的情況下,通過哈希函數計算出來的 哈希地址,一定也是確定的。如圖中的 dd 已經確定在 1002 位置了,那么就不可能再占據 1003 位置。

思考一下,如果有另外一個元素 ee 來了,它的哈希地址也落在 1002 位置,怎么辦呢?

hashCode 有什么用?

其實,上圖就已經可以說明一些問題了。我們通過一個 key 計算出它的 hashCode 值,就可以唯一確定它在哈希表中的位置。這樣,在查詢時,就可以直接定位到當前元素,提高查詢效率。

現在我們假設有這樣一個場景。我們需要在內存中的一塊兒區域存放 10000 個不同的元素(以aa,bb,cc,dd 等為例)。那怎么實現不同的元素插入,相同的元素覆蓋呢?

我們最容易想到的方法就是,每當存一個新元素時,就遍歷一遍已經存在的元素,看有沒有相同的。這樣雖然也是可以實現的,但是,如果已經存在了 9000 個元素,你就需要去遍歷一下這 9000 個元素。很明顯,這樣的效率是非常低下的。

我們轉換一種思路,還是以上圖為例。若來了一個新元素 ff,首先去計算它的 hashCode 值,得出為 1003 。發現此處還沒有元素,則直接把這個新元素 ff 放到此位置。

然后,ee 來了,通過計算哈希值得到 1002 。此時,發現 1002 位置已經存在一個元素了。那么,通過 equals 方法比較它們是否相等,發現只有一個 dd 元素,很明顯和 ee 不相等。那么,就把 ee 元素放到 dd 元素的后邊(可以用鏈表形式存放)。

我們會發現,當有新元素來的時候,先去計算它們的哈希值,再去確定存放的位置,這樣就可以減少比較的次數。如 ff 不需要比較, ee 只需要和 dd 比較一次。

當元素越來越多的時候,新元素也只需要和當前哈希值相同的位置上,已經存在的元素進行比較。而不需要和其他哈希值不同的位置上的元素進行比較。這樣就大大減少了元素的比較次數。

圖中為了方便,畫的哈希表比較小。現在假設,這個哈希表非常的大,例如有這么非常多個位置,從 1001 ~ 9999。那么,新元素插入的時候,有很大概率會插入到一個還沒有元素存在的位置上,這樣就不需要比較了,效率非常高。但是,我們會發現這樣也有一個弊端,就是哈希表所占的內存空間就會變大。因此,這是一個權衡的過程。

有心的同學可能已經發現了。我去,上邊的這個做法好熟悉啊。沒錯,它就是大名鼎鼎的 HashMap 底層實現的思想。對 HashMap 還不了解的,趕緊看這篇文章理一下思路。HashMap 底層實現原理及源碼分析

所以,hashCode 有什么用。很明顯,提高了查詢,插入元素的效率呀。

equals 和 == 有什么區別?

這是萬年不變,經久不衰的經典面試題了。讓我油然想起,當初為了面試,背誦過的面經了,簡直是一把心酸一把淚。現在還能記得這道題的標準答案:equals 比較的是內容, == 比較的是地址。

當時,真的就只是背答案,知其然而不知其所以然。再往下問,為什么要重寫 equals ,就懵逼了。

首先,我們應該知道 equals 是定義在所有類的父類 Object 中的。

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

可以看到,它的默認實現,就是 == ,這是用來比較內存地址的。所以,如果一個對象的 equals 不重寫的話,和 == 的效果是一樣的。

我們知道,當創建兩個普通對象時,一般情況下,它們所對應的內存地址是不一樣的。例如,我定義一個 User 類。

public class User {
    private String name;
    private int age;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public User() {

    }
}

public class TestHashCode {
    public static void main(String[] args) {
        User user1 = new User("zhangsan", 20);
        User user2 = new User("lisi", 18); 

        System.out.println(user1 == user2);
        System.out.println(user1.equals(user2));
    }
}
// 結果: false	false

很明顯,zhangsan 和 lisi 是兩個人,兩個不同的對象。因此,它們所對應的內存地址不同,而且內容也不相等。

注意,這里我還沒有對 User 重寫 equals,實際此時 equals 使用的是父類 Object 的方法,返回的肯定是不相等的。因此,為了更好地說明問題,我僅把第二行代碼修改如下:

//User user2 = new User("lisi", 18);
User user2 = new User("zhangsan", 20);

讓 user1 和 user2 的內容相同,都是 zhangsan,20歲。按我們的理解,這雖然是兩個對象,但是應該是指的同一個人,都是張三。但是,打印結果,如下:

這有悖于我們的認知,明明是同一個人,為什么 equals 返回的卻不相等呢。因此,此時我們就需要把 User 類中的 equals 方法重寫,以達到我們的目的。在 User 中添加如下代碼(使用 idea 自動生成代碼):

public class User {
    ... //省略已知代碼
        
    @Override
    public boolean equals(Object o) {
        //若兩個對象的內存地址相同,則說明指向的是同一個對象,故內容一定相同。
        if (this == o) return true;
        //類都不是同一個,更別談相等了
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        //比較兩個對象中的所有屬性,即name和age都必須相同,才可認為兩個對象相等
        return age == user.age &&
                Objects.equals(name, user.name);
    }
   
}
//打印結果:  false 	true

再次執行程序,我們會發現此時 equals 返回 true ,這才是我們想要的。

因此,當我們使用自定義對象時。如果需要讓兩個對象的內容相同時,equals 返回 true,則需要重寫 equals 方法。

為什么要重寫 equals 和 hashCode ?

在上邊的案例中,其實我們已經說明了為什么要去重寫 equals 。因為,在對象內容相同的情況下,我們需要讓對象相等。因此,不能用 Object 類的默認實現,只去比較內存地址,這樣是不合理的。

那 hashCode 為什么要重寫呢? 這就涉及到集合,如 Map 和 Set (底層其實也是 Map)了。

我們以 HashMap JDK1.8的源碼來看,如 put 方法。

我們會發現,代碼中會多次進行 hash 值的比較,只有當哈希值相等時,才會去比較 equals 方法。當 hashCode 和 equals 都相同時,才會覆蓋元素。get 方法也是如此(先比較哈希值,再比較equals),

只有 hashCode 和 equals 都相等時,才認為是同一個元素,找到并返回此元素,否則返回 null。

這也對應 “hashCode 有什么用?”這一小節。 重寫 equals 和 hashCode 的目的,就是為了方便哈希表這樣的結構快速的查詢和插入。如果不重寫,則無法比較元素,甚至造成元素位置錯亂。

重寫了 equals ,就必須要重寫 hashCode 嗎?

答案是肯定的。首先,在上邊的 JDK 源碼注釋中第第二點,我們就會發現這句說明。其次,我們嘗試重寫 equals ,而不重寫 hashCode 看會發生什么現象。

public class TestHashCode {
    public static void main(String[] args) {
        User user1 = new User("zhangsan", 20);
        User user2 = new User("zhangsan", 20);

        HashMap<User, Integer> map = new HashMap<>();
        map.put(user1,90);
        System.out.println(map.get(user2));
    }
}
// 打印結果: null

對于代碼中的 user1 和 user2 兩個對象來說,我們認為他是同一個人張三。定義一個 map ,key 存儲 User 對象, value 存儲他的學習成績。

當把 user1 對象作為 key ,成績 90 作為 value 存儲到 map 中時,我們肯定希望,用 key 為 user2 來取值時,得到的結果是 90 。但是,結果卻大失所望,得到了 null 。

這是因為,我們自定義的 User 類,雖然重寫了 equals ,但是沒有重寫 hashCode 。當 user1 放到 map 中時,計算出來的哈希值和用 user2 去取值時計算的哈希值不相等。因此,equals 方法都沒有比較的機會。認為他們是不同的元素。然而,其實,我們應該認為 user1 和 user2 是相同的元素的。

用圖來說明就是,user1 和 user2 存放在了 HashMap 中不同的桶里邊,導致查詢不到目標元素。

因此,當我們用自定義類來作為 HashMap 的 key 時,必須要重寫 hashCode 和 equals 。否則,會得到我們不想要的結果。

這也是為什么,我們平時都喜歡用 String 字符串來作為 key 的原因。 因為, String 類默認就幫我們實現了 equals 和 hashCode 方法的重寫。如下,

// String.java
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        //從前向后依次比較字符串中的每個字符
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
		//把字符串中的每個字符都取出來,參與運算
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        //把計算出來的最終值,存放在hash變量中。
        hash = h;
    }
    return h;
}

重寫 equals 時,可以使用 idea 提供的自動代碼,也可以自己手動實現。

public class User {
    ... //省略已知代碼
        
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
   
}
//此時,map.get(user2) 可以得到 90 的正確值

在重寫了 hashCode 后,使用自定義對象作為 key 時,還需要注意一點,不要在使用過程中,改變對象的內容,這樣會導致 hashCode 值發生改變,同樣得不到正確的結果。如下,

public class TestHashCode {
    public static void main(String[] args) {
        User user = new User("zhangsan", 20);

        HashMap<User, Integer> map = new HashMap<>();
        map.put(user,90);
        System.out.println(map.get(user));
        user.setAge(18); //把對象的年齡修改為18
        System.out.println(map.get(user));
    }
}
// 打印結果:
// 90
// null

會發現,修改后,拿到的值是 null 。這也是,hashCode 源碼注釋中的第一點說明的,hashCode 值不變的前提是,對象的信息沒有被修改。若被修改,則有可能導致 hashCode 值改變。

此時,有沒有聯想到其他一些問題。比如,為什么 String 類要設計成不可以變的呢?這里用 String 作為 HashMap 的 key 時,可以算作一個原因。你肯定不希望,放進去的時候還好好的,取出來的時候,卻找不到元素了吧。

String 類內部會有一個變量(hash)來緩存字符串的 hashCode 值。只有字符串不可變,才可以保證哈希值不變。

hashCode 相等時,equals 一定相等嗎?

很顯然不是的。在 HashMap 的源碼中,我們就能看到,當 hashCode 相等時(產生哈希碰撞),還需要比較它們的 equals ,才可以確定是否是同一個對象。因此,hashCode 相等時, equals 不一定相等 。

反過來,equals 相等的話, hashCode 一定相等嗎? 那必須的。equals 都相等了,那說明在 HashMap 中認為它們是同一個元素,所以 hashCode 值必須也要保證相等。

結論:

  • hashCode 相等,equals 不一定相等。
  • hashCode 不等,equals 一定不等。
  • equals 相等, hashCode 一定相等。
  • equals 不等, hashCode 不一定不等。

關于最后這一點,就是 hashCode 源碼注釋中提到的第三點。當 equals 不等時,不用必須保證它們的 hashCode 也不相等。但是為了提高哈希表的效率,最好設計成不等。

因為,我們既然知道它們不相等了,那么當 hashCode 設計成不等時。只要比較 hashCode 不相等,我們就可以直接返回 null,而不必再去比較 equals 了。這樣,就減少了比較的次數,無疑提高了效率。

結尾

以上就是 hashCode 和 equals 相關的一些問題。相信已經可以解答你心中的疑惑了,也可以和面試官侃侃而談。再也不用擔心,面試官說換人了。

posted @ 2020-06-23 20:01  煙雨星空  閱讀(425)  評論(2編輯  收藏
最新chease0ldman老人|无码亚洲人妻下载|大香蕉在线看好吊妞视频这里有精品www|亚洲色情综合网