昨天花時間在 debug 一個非常詭異的問題。Java 代碼裡面的一個 HashSet 集合裡面命令包含這個元素，equals、hashCode 都一樣，甚至對象的 id 都是一樣的，但是 contains 方法返回的結果總是 false ！最後花了很多時間，百思不得其解，一度懷疑我生活在 Matrix 裡面。最後發現問題的一刻也恍然大悟，發現這是一個我早就知道的問題。這必定成為我職業生涯的一個汙點，所以我打算記錄一下這個問題。
先賣個關子吧，我來描述一下問題的背景，看你能否想到答案。
問題是這樣的，我們用 JGraphT 來解決一個圖的問題。這個圖是我們從應用的調用關係鏈中生成的，生成之後會導出到 json，放到一個地方。然後所有的計算節點都可以通過這個 json 來 load 圖，就不用每個節點都去清洗一遍了。一個節點清洗過後，所有的節點都從這裡加載。問題主要出現圖的導出和導入，圖中每個節點都有一個 id，一開始我用應用的名字作為 id，導出到 json，但是導入的時候發現 Importer 會重新生成 ID，圖的關係是對的，但是節點的 ID 從字符串變成了重新生成的 id 了，那麼應用名字的信息就丟失了。我又給節點加上 name 屬性，期望這個屬性 import 之後還是好的。結果發現 import 只是 import 圖的關係，並沒有 import 進來其他屬性（這個庫看起來很 nice 啊，不知道為啥文檔這麼差，import 的細節都沒有文檔）。於是我參考 Test 裡面的做法，用一個 Map 存下來節點的其他屬性。然後在 import 完成之後，將這些屬性 set 進去。
OK，總結一下，簡單來說就是，我先從 json 導入進圖，導入的時候也存下來每個節點的屬性（其實就是 name），導入之後遍歷圖的節點，將每個屬性設置進去。
問題就出現了。我用圖來找最短路徑的時候報錯：節點不存在！
定位到庫裡面，判斷節點不存在的 contains函數是這麼寫的：
我 debug 了這個 Set 和 v 的關係，發現 Set 中的一個元素，跟 v 是一模一樣的！對象 id 都是一樣的。
equals 返回值是一樣的：
hashCode 返回值也一樣：
但是這個 contains 函數就是返回 false。
為了讓這個問題更明顯一些，我把這個問題簡化成下面這段 Java 代碼，可以直接運行：
<code>import java.util.HashSet;
import java.util.Objects;
public class Vertex {
private String id;
private String name;
public Vertex(String id, String name) {
this.id = id;
this.name = name;
}
public static void main(String[] args) {
Vertex app1 = new Vertex("1", null);
Vertex app2 = new Vertex("2", null);
Vertex app3 = new Vertex("3", null);
// 模擬我們從 json 載入這個圖的過程
// 這個時候 name 是不在圖裡面的
HashSet<vertex> sets = new HashSet<>();
sets.add(app1);
sets.add(app2);
sets.add(app3);
// 載入之後，我們會將屬性設置好，歡迎應用名字的信息
app1.name = "app1";
app2.name = "app2";
app3.name = "app3";
// 返回 false
System.out.println(sets.contains(app1));
System.out.println(sets.stream().filter(x -> x.hashCode() == app1.hashCode()).findFirst());
System.out.println(sets.stream().filter(x -> x.equals(app1)).findFirst());
}
@Override public boolean equals(Object o) {
if (this == o) { return true; }
if (o == null || getClass() != o.getClass()) { return false; }
Vertex vertex = (Vertex) o;
return Objects.equals(id, vertex.id) &&
Objects.equals(name, vertex.name);
}
@Override public int hashCode() {
return Objects.hash(id, name);
}
}/<vertex>/<code>
<code>運行結果如下：$ javac Vertex.java
$ java Vertex
false
Optional[Vertex@2dd3e0]
Optional[Vertex@2dd3e0]明明 equals 和 hashCode 都一樣，為什麼 contains 就是 false 呢？/<code>
答案就在查找 Hash 表的方式。我之前寫過一篇文章《Hash碰撞和解決策略》，介紹如果發生 hash 碰撞，那麼 hash 表一般會通過某種方式存放 hash 相同的元素。這就要求，在 hash 表中查找元素的時候，必須滿足以下兩個條件，才算是找到了元素：
- 按照 hash 值能找到這個元素所在的 hash 位置，但是這個位置存放著很多 hash 值相同的元素，所以還要滿足2；
- 必須滿足相等（equals）。
Hash碰撞和解決策略: kawabangga.com/posts/2493
HashSet 其實就是沒有 value 的 HashMap，本質上也是個 hash 表，所以 contains 要返回 true，也必須滿足上面兩個條件。元素在存進去的時候，name 是空的，按照 name 是 null 得到了一個 hash 值，放到了 HashMap 的一個地方，記作位置 A。然後我後來修改 name 的值，再 hash 的時候，就會得到另一個 hash 值，記作位置 B.。然後 contains 去位置 B 一看，這個位置是個null，就認為這個元素不在集合中了。
為什麼 hashCode 和 equals 返回都是相等的呢？因為我們先按照 name = null 保存了進去，保存的時候 hash 值已經確定了。後來修改了 name，hash 值已經不會修改（不會在 HashSet 裡面移動的）。雖然對象即使是同一個對象，但是 hash 值已經和放進去的時候變了。拿現在的對象（Set裡面的那個對象，和現在的要確定是否被 contains 的對象，都是“現在的對象”，name 已經被修改了的）來對比 hash 值肯定是相等的，但是已經和放進去的時候的那個 hash 值不同了。去看 HashSet 中，現在的這個 hash 值的位置，肯定是個 null，所以判斷為元素不存在。
簡單總結一下，就是放入 Hash 中的元素，一定要是不可修改的（這個和 Python 為什麼 list 不能作為字典的 key？的原理是一樣的）。如果修改了，那這個元素就從集合中找不回來了。
最後，從這個故事中我們能學到什麼呢？
感覺學不到什麼，現在回想起來就跟自己的智商受到了降維打擊一樣。
哦，對了。如果你看懂了這個問題，那麼就會理解，之所以找不到這個元素是因為這個元素放進去的時候的 hashCode 和現在的這個元素的 hashCode 已經不一樣了。我不禁回憶起另外一個問題：
有三個人去住旅館，住三間房，每一間房$10元，於是他們一共付給老闆$30，第二天，老闆覺得三間房只需要$25元就夠了，於是叫小弟退回$5給三位客人。
誰知小弟貪心，只退回每人$1，自己偷偷拿了$2，這樣一來便等於那三位客人每人各花了九元，於是三個人一共花了$27，再加上小弟獨吞了不$2，總共是$29。可是當初他們三個人一共付出$30那麼還有$1呢？
閱讀更多 Java從算法到架構 的文章
