为什么JavaSet上的remove()方法不起作用

html5 • • 问答

我有以下代码：

    Set<Set<Integer>> groups = new HashSet<>();

    for (int[] edge : edges) {
        Set<Integer> match1 = null;
        Set<Integer> match2 = null;

        for(Set<Integer> group : groups) {
            if(group.contains(edge[0])) match1 = group;
            if(group.contains(edge[1])) match2 = group;
        }

        if(match1 != null && match1 == match2) {
            result = edge;
        }else if(match1 != null && match2 != null && match1 != match2) {
            match1.addAll(match2);
            groups.remove(match2);     <---- This does not remove match2 from set
        }else{
            Set<Integer> newGroup = new HashSet<>();
            newGroup.add(edge[0]);
            newGroup.add(edge[1]);
            groups.add(newGroup);
        }
        
        .........
    }

该groups是一个集整数集的。

但是，groups.remove(match2) 方法不会从组中删除整数集。

这里发生了什么？

回答

引用Set接口文档：

注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的元素，则不会指定集合的​​行为。此禁止的一个特殊情况是不允许集合将自身包含为元素。

当您match1在addAll()调用仍在外部Set. 突变会导致哈希码在外部Set不知道的情况下更改，因此内部Set现在位于错误的哈希桶中，并且在您尝试在后续迭代中删除它时无法找到。

作为解决方法，您可以将其删除，然后调用addAll()，然后再次添加。在内部，这将导致它被放置在正确的哈希桶中以获取新的哈希码。

顺便说一句，您似乎正在实施连接组件检测算法。您可以使用不相交的森林数据结构更有效地做到这一点。How to store each set in a disjoint set forest 中有一些很好的伪代码。

以上是为什么JavaSet上的remove()方法不起作用的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>