攜手創作，共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第1天，點選檢視活動詳情

前言

自信滿滿的體驗了位元組的一面，挫敗的一輪遊了。其中遇到一個程式碼題，其實考的也不是很難，但是比較考察細節，知識的理解度。感覺很值得和大家分享一下。

面試全經過&題目

```java public class Test { class Item{

    private int code = 1;

    public Item(int code){
        this.code =  code;
    }

    override public int hashCode() {
        return code;
    }
}

public static void main(String[] args) {
    Set<Item> set = new HashSet<>();
    set.add(new Item(0));
    set.add(new Item(0));
    set.add(new Item(1));

    System.out.println(set.size());

}

}

```

面試官：這有一道程式碼題，你看下，你覺得最終會輸出什麼呢？
我：2
面試官：為什麼？談談原因？
我：因為重寫了hash,HashSet 內部會認為傳遞同樣的code是同一個物件，所以第一個new Item(0)和第二個new Item(0) 會被認為是同一個物件，然後後者會覆蓋前者，所以是2
面試官：實際上這段程式碼是不能執行的，現在需要你修改正確，並輸出結果
我：編寫程式碼中....(Item 改成了 static,override 關鍵字修改為 @Override註釋)
我：改完了，執行一看，發現是 3，你說尷尬不尷尬.....
面試官：你覺得為啥和你之前設想的不一樣
我：應該是還需要實現equals方法
面試官：為什麼呢？
我：...

問題解惑

雖然中間有些修改語法的操作，但是那對於大家應該都是小Case,主要的核心問題是：

HashSet 中add() 方法中對同一物件的判定邏輯
hashCode() 和 equals() 的理解

接下來一一都為大家介紹下。

HashSet.add() 內部邏輯

實際上 HashSet 的實現是依靠 HashMap 實現的，具體邏輯可以看下面的程式碼： ``` public class HashSet{ //內部實現依靠HashMap private transient HashMap map;

//固定的value值
private static final Object PRESENT = new Object();

HashSet(int initialCapacity, float loadFactor, boolean dummy) { //初始化的時候宣告 map = new LinkedHashMap<>(initialCapacity, loadFactor); }

//新增方法，實際上，將資料作為key儲存到  HashMap 中
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

} ```

所以咱們要看的邏輯，實際上就 HashMap 怎麼判定 key 相等的，具體程式碼在 java.util.HashMap#putVal 中

看下分支條件

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

分解下：

p.hash == hash

先看這個hash 是什麼？ HashMap() 中提供了一個雜湊演算法，將傳入的 key 通過這個演算法轉成了一個 Int 值，然後儲存到資料節點中了。

雜湊演算法的實現是將 key 的 hashCode() 值右位移16位，然後和自身異或。為啥這樣實現的原理很複雜，此處按下不表，但是可以明確知道的是，內部使用了 hashCode()，所以這個方法很重要。

//put 的時候進行hash() public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //hash演算法的實現 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

(k = p.key) == key || (key != null && key.equals(k))

程式碼中內部賦值了k，看起來有點長，咱們簡化以下，其實發現就兩個條件 p.key == key 和 key.equals(p.key)，兩者只要有一個成立就可以了。

所以根據以上分析，只有 hashCode() 和 equals() 兩者都相等，HashMap 才會認為是同個key。

hashCode() 和 equals() 的理解

首先它們是什麼？

這倆方法都是 Object 類內的方法，它們本身代表的含義是

```

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

@HotSpotIntrinsicCandidate
public native int hashCode();

```

equals() ：內部使用了 “==”。判斷是否是同個物件，如果是值型別，判斷內容是否一致，如果是引用型別，則是引用地址是否相等。 hashCode()：一個本地方法，主要看native 中的實現。

之前我理解的是，hashCode返回的就是物件的儲存地址，但是看到一篇文章上公佈了 JVM中程式碼的實現，發現事實並不是這樣。

它內部提供了多種實現方式供選擇，可以通過JVM啟動引數中新增-XX:hashCode=x，但是 JDK8 預設的是 hashCode=5

隨機數
記憶體地址做移位再和一個隨機數做異或
固定值1
自增序列的當前值
記憶體地址
當前執行緒有關的一個隨機數+三個確定值，運用xorshift隨機數演算法得到的一個隨機數。

以上是個知識小拓展吧，問題核心是 hashCode()這個方法為什麼會被設計出來？

然後看為什麼？兩個方法的設計目的

關於 hashCode()方法的使用，我目前只在 HashMap 的原始碼中看到過。以及在原始碼中對此方法的註釋中，也可以窺見一斑。它的主要目的是為了服務於散列表的實現，例如最典型的 HashMap。

那 HashMap 特殊在哪裡？這個取決於它的資料結構的特殊-雜湊表。

首先從最基礎的資料結構看起，我們知道陣列和連結串列的概念，但是這兩者使用起來各有優劣，例如： - 陣列查詢遍歷快，但是插入刪除慢。 - 連結串列插入刪除快，查詢遍歷慢。

咱們用的時候，需要根據場景決定使用哪個。但是有時候就是既要查詢快，又要插入刪除快。有沒有一種東西，能夠將兩者的優點結合起來呢？

有，那就是雜湊表。它使用使用陣列查詢，連結串列插入和刪除，充分結合了這兩者的優點。

雜湊表有多種不同的實現方法，最常用的一種方法——拉鍊法，我們可以理解為“連結串列的陣列”，HashMap 用的正是這個一個方法，示意圖如下：

雜湊表的一個關鍵定義是：

雜湊表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的資料結構。也就是說，它通過把關鍵碼值對映到表中一個位置來訪問記錄，以加快查詢的速度。這個對映函式叫做雜湊函式，存放記錄的陣列叫做散列表

生成這個關鍵碼值(Key value)的地方就用到了 hashCode()。大家從上面的結構示意圖上也可以知道，不同的物件 hashCode 有可能是一致的。所以會在同個資料下標下，多個數據節點串在一起。這就是所謂的雜湊碰撞。

好的雜湊演算法要儘量避免雜湊碰撞，但是呢，也從來不能保證說是完全避免的，這可能就是提高效能必須要付出的代價吧。

那我們使用 equals() 代替 hashCode() 可以嗎？這個是記憶體地址是不是就可以減少碰撞的機率了呢？

答案是不可以！！！

有以下原因：

equals() 的預設實現是用的記憶體地址，但是也有很多類改寫了，例如 String 就修改了。
equals() 允許重寫後，邏輯可能會變得複雜，所以就效能上來說，大概率沒有 hashCode() 的效能高。

所以這兩個方法的職責是完全不一樣的 - equals() 主要負責判斷是否是同個物件，絕對可靠，但是效能可能較差 - hashCode() 主要負責在提高判斷效率（主要是在雜湊表資料結構中），但是隻能大概率保證是同個物件，不可靠

然後再看Hashmap 原始碼中的判斷邏輯，細節就來了,優先判斷 hash,hash 一樣再判斷 equals(),這樣就可以提高效能，真是妙啊！

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

對應咱們經常在網上看到的兩者關係總結，是不是就十分清晰了呢 - equals()相等，hashCode()肯定相等 - hashCode()相等，equals()不一定相等

然後怎麼用？重寫 equals() 和 hashCode() 的注意事項

在多數情況下，這兩個函式是不用考慮的。直接使用它們的預設設計就能夠了。

但凡事總有特殊，例如 String 就針對其進行了重寫。

``` // String.java public boolean equals(Object anObject) { //記憶體地址相等，肯定是同個物件 if (this == anObject) { return true; } //否則逐個判斷字元是否一致 if (anObject instanceof String) { String aString = (String)anObject; if (!COMPACT_STRINGS || this.coder == aString.coder) { return StringLatin1.equals(value, aString.value); } } return false; }

public int hashCode() {
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

//StringLatin1.java

//雜湊演算法的真正實現
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

//逐個判斷字元是否一致
public static boolean equals(byte[] value, byte[] other) {
    if (value.length == other.length) {
        for (int i = 0; i < value.length; i++) {
            if (value[i] != other[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

```

除了原始碼，真實專案中，也有重寫的需求，例如我負責的購物車，購物車商品模型中，針對是否是同個商品物件的邏輯，就寫在了 equals() 方法中。

一般咱們的需求出發點，基本都是需要改造 equals()。但是一旦修改了 equals(), 就要一定要考慮修改 hashCode()，不然你用在散列表中就可能出現奇奇怪怪的問題。

equals()重寫的時候需要滿足以下規則：

記憶體地址相同，一定返回true (使用“==”操作符檢查)
型別不一致，一定返回false(使用instanceof 操作符檢查)
型別轉換後，判斷類中每個關鍵屬性，符合預設，返回 true , 否則 false

hashCode()重寫的時候需要滿足以下規則：

保證同一個物件，多次呼叫 Hashcode 是一致的。
equals()相等，hashCode()肯定相等

另外，阿里巴巴開發規範也有對這倆方法的重寫制訂了一些規範，咱們開發的時候也可以做個參考：

總結

以上都是我的事後分析，再回頭看這個面試題，需要做的就是

不受重寫 hashCode() 的干擾，給出正確的列表長度答案
說出對 hashCode() 和 equals() 的理解

以及最關鍵的，基礎知識理解透徹的重要性，平時要認真對待，多學習多思考，多問為什麼。

參考資料

Effective Java 中文版

Java Object.hashCode()返回的是物件記憶體地址？

淺談Java中的hashcode方法

看似簡單的hashCode和equals面試題，竟然有這麼多坑！

最簡單的易懂的技術乾貨，好玩的事情，都會在公眾號「淺淺同學的開發筆記」分享，快來呀～期待與你共同成長！

一道程式碼題對考察Java HashCode 的深度理解

前言