集合里的元素怎么“不见了”？

链接：/posts/3941

程序员小乐(ID:)第802次推文 图片来自百度

往日回顾：小米回应暴力裁员：已提前三个月通知不续签合同，并且给了N+1补偿

正文

昨天花时间在 debug 一个非常诡异的问题。Java 代码里面的一个 集合里面命令包含这个元素，、 都一样，甚至对象的 id 都是一样的，但是 方法返回的结果总是 false ！最后花了很多时间，百思不得其解，一度怀疑我生活在 里面。最后发现问题的一刻也恍然大悟，发现这是一个我早就知道的问题。这必定成为我职业生涯的一个污点，所以我打算记录一下这个问题。

先卖个关子吧，我来描述一下问题的背景，看你能否想到答案。

问题是这样的，我们用 来解决一个图的问题。这个图是我们从应用的调用关系链中生成的，生成之后会导出到 json，放到一个地方。然后所有的计算节点都可以通过这个 json 来 load 图，就不用每个节点都去清洗一遍了。一个节点清洗过后，所有的节点都从这里加载。问题主要出现图的导出和导入，图中每个节点都有一个 id，一开始我用应用的名字作为 id，导出到 json，但是导入的时候发现 会重新生成 ID，图的关系是对的，但是节点的 ID 从字符串变成了重新生成的 id 了，那么应用名字的信息就丢失了。我又给节点加上 name 属性，期望这个属性 之后还是好的。结果发现 只是 图的关系，并没有 进来其他属性（这个库看起来很 nice 啊，不知道为啥文档这么差， 的细节都没有文档）。于是我参考 Test 里面的做法，用一个Map存下来节点的其他属性。然后在 完成之后，将这些属性set进去。

OK，总结一下，简单来说就是，我先从 json 导入进图，导入的时候也存下来每个节点的属性（其实就是 name），导入之后遍历图的节点，将每个属性设置进去。

问题就出现了。我用图来找最短路径的时候报错：节点不存在！

定位到库里面，判断节点不存在的函数是这么写的：

我 debug 了这个Set和v的关系，发现Set中的一个元素，跟v是一模一样的！对象id都是一样的。

返回值是一样的：

返回值也一样：

但是这个函数就是返回false。

为了让这个问题更明显一些，我把这个问题简化成下面这段Java 代码，可以直接运行：

			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 sets = new HashSet<>();sets.add(app1);sets.add(app2);sets.add(app3);// 载入之后，我们会将属性设置好，欢迎应用名字的信息app1.name = "app1";app2.name = "app2";app3.name = "app3";// 返回 falseSystem.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());}@Overridepublic 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);}@Overridepublic int hashCode() {return Objects.hash(id, name);}
}

运行结果如下：

$ javac Vertex.java
$ java Vertex
false
Optional[Vertex@2dd3e0]
Optional[Vertex@2dd3e0]

明明和都一样，为什么就是false呢？

答案就在查找 Hash 表的方式。我之前写过一篇文章《Hash碰撞和解决策略》，介绍如果发生 hash 碰撞，那么 hash 表一般会通过某种方式存放 hash 相同的元素。这就要求，在 hash 表中查找元素的时候，必须满足以下两个条件，才算是找到了元素：

按照 hash 值能找到这个元素所在的 hash 位置，但是这个位置存放着很多 hash 值相同的元素，所以还要满足2；

必须满足相等（）。

Hash碰撞和解决策略:/posts/2493

其实就是没有 value 的，本质上也是个 hash 表，所以要返回 true，也必须满足上面两个条件。元素在存进去的时候，name是空的，按照name是null得到了一个 hash 值，放到了的一个地方，记作位置 A。然后我后来修改name的值，再 hash 的时候，就会得到另一个 hash 值，记作位置 B.。然后去位置 B 一看，这个位置是个null，就认为这个元素不在集合中了。

为什么和返回都是相等的呢？因为我们先按照name = null保存了进去，保存的时候 hash 值已经确定了。后来修改了name，hash 值已经不会修改（不会在里面移动的）。虽然对象即使是同一个对象，但是 hash 值已经和放进去的时候变了。拿现在的对象（Set里面的那个对象，和现在的要确定是否被的对象，都是“现在的对象”，name已经被修改了的）来对比 hash 值肯定是相等的，但是已经和放进去的时候的那个 hash 值不同了。去看中，现在的这个 hash 值的位置，肯定是个null，所以判断为元素不存在。

简单总结一下，就是放入 Hash 中的元素，一定要是不可修改的（这个和 为什么 list 不能作为字典的 key？的原理是一样的）。如果修改了，那这个元素就从集合中找不回来了。

最后，从这个故事中我们能学到什么呢？

感觉学不到什么，现在回想起来就跟自己的智商受到了降维打击一样。

哦，对了。如果你看懂了这个问题，那么就会理解，之所以找不到这个元素是因为这个元素放进去的时候的 和现在的这个元素的 已经不一样了。我不禁回忆起另外一个问题：

有三个人去住旅馆，住三间房，每一间房$10元，于是他们一共付给老板$30，第二天，老板觉得三间房只需要$25元就够了，于是叫小弟退回$5给三位客人。

谁知小弟贪心，只退回每人$1，自己偷偷拿了$2，这样一来便等于那三位客人每人各花了九元，于是三个人一共花了$27，再加上小弟独吞了$2，总共是$29。可是当初他们三个人一共付出$30那么还有$1呢？

欢迎在留言区留下你的观点，一起讨论提高。如果今天的文章让你有新的启发，学习能力的提升上有新的认识，欢迎转发分享给更多人。

欢迎各位读者加入订阅号程序员小乐技术群，在后台回复“加群”或者“学习”即可。

猜你还想看

阿里、腾讯、百度、华为、京东最新面试题汇集

必须要掌握的 异常处理

3.4k星，200余行代码，让你实时从视频中隐身

一次SQL查询优化原理分析（900W+数据，从17s到300ms）

关注订阅号「程序员小乐」，收看更多精彩内容

嘿，你在看吗？