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

昨天花时间在 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 代码：

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);
    }
}

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);

}

运行结果如下：

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

$ javac Vertex.java

$ java Vertex

false

Optional[Vertex@2dd3e0]

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

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

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

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呢？

“集合里的元素怎么“不见了”？”已经有10条评论


piglei on 2020年2月27日 at 09:48 said:

想起以前读过一篇很棒的文章：https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/ 。python 世界的同一个问题。
- Reply
  
  laixintao on 2020年2月27日 at 21:30 said:
  
  Hash 表的一百种死法… 我开始感受到所有对象都是不可变的语言的好处了……

davidfeng on 2020年2月28日 at 05:35 said:

也不至于是“污点”那么严重吧……很多时候都这样，事后觉得很明显的，当时就是想不出来……
- Reply
  
  laixintao on 2020年2月28日 at 10:47 said:
  
  哈哈，开玩笑的

jiang on 2020年2月28日 at 10:21 said:

没找出来问题就是“污点”，找出来就变成“有趣的经历”了
- Reply
  
  laixintao on 2020年2月28日 at 10:47 said:
  
  有趣的污点

laike9m on 2020年2月28日 at 15:25 said:

允许把 mutable 变量写入 set 是不是 API 设计的失误？
- Reply
  
  laixintao on 2020年2月28日 at 15:30 said:
  
  节点的类型（Vertex）是允许用户自己定义的，我自己定义的就可以写入了。但问题就是它这个图内部用的是 Set 来表示所有边的合集，文档中却没有警告节点要是 Unmutable 的……
  - Reply
    
    laike9m on 2020年2月28日 at 16:04 said:
    
    我的意思是，Python 和 Java 都允许用户用自定义的 class 作为 dict/map/set 的 key，但实际上就会带来本文中的这种问题。我觉得这似乎是一个设计上的失误，或者也可以说没有 immutable class 是设计失误。
    - Reply
      
      laixintao on 2020年2月28日 at 21:24 said:
      
      是的，我开始感受到像 Rust Elixir 这种所有对象都是不可变的语言的好处了……

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

相关文章:

“集合里的元素怎么“不见了”？”已经有10条评论

Leave a comment 取消回复

2024 年 11 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30