Java Collections API HashSet 移除方法

Question

我在使用 Java Collections API 时遇到了这个问题。基本上，这是用于实现 Kruskal 算法以查找 MST 的支持方法。我创建了这个类来实现联合/查找算法。

我的问题是，因为我能够找到解决方法，所以有人知道为什么“union”方法中的 remove 方法无法始终如一地工作的任何原因。那是在运行时它会删除一些元素而不是其他元素。例如，我为涉及城市的任务实现了这个，它似乎不喜欢删除一些城市。特别是它反复偶然发现了几个不同的集合，但总是相同的。我想知道这是否是一个对象引用问题，即我是否在测试错误的东西，但我无法绕过它。

我知道我的其余工作是正确的，因为我能够用消除元素的循环替换它，并且算法完美执行。但是，可能性能稍差。

我想知道是否有人能看出错误。另外我应该注意，我从不同的类调用它，但是，调用是使用使用 find 方法检索的元素进行的。请注意，find 方法必须运行良好，因为只需更改 remove 方法即可使整个过程正常运行，即它正在查找并返回适当的对象。

谢谢

奥斯卡

/*
 * A constructor for creating a new object of this class.
 */
DisjointSets()
{
    underlying = new HashSet<HashSet<String>>();
}

/*
 * A method for adding a set to this DisjointSets object
 */
void add(HashSet<String> h)
{
    underlying.add(h);
}

/*
 * A method for finding an element in this DisjointSet object.
 */
HashSet<String> find(String s)
{
    // Check each set in the DisjointSets object
    for(HashSet<String> h: underlying)
    {
        if(h.contains(s))
        {
            return h;
        }
    }
    return null;
}

/*
 * A method for combining to subsets of the DisjointSets
 */
void union(HashSet<String> h1, HashSet<String> h2)
{
    System.out.print("CHECK ON DS\n");
    System.out.print("*********************\n");
    System.out.print("H1 is : { ");
    for (HashSet<String> n: underlying) 
    {
        System.out.print("Set is : { ");
        for (String h : n) 
        {
            System.out.print(h + " , ");
        }
        System.out.print("} \n ");
    }
    // Add the objects of h1 to h2
    // DOES NOT WORK CONSISTENTLY
            h1.addAll(h2);
    underlying.remove(h2);
}

我把它换成了

HashSet<HashSet<String>> temp = new HashSet<HashSet<String>>();
        for(HashSet<String> f: underlying)
        {
            if(f != h2)
            {
                temp.add(f);
            }
        }
        underlying = temp;

Answer 1

问题是，当您修改其中一个嵌套 HashSet 的内容时，您搞砸了外部 HashSet 的内部结构(因为嵌套 HashSet 的 hashCode() 已更改)。为了正确维护此集合，无论何时您想要修改其中一个嵌套的 HashSet，您都必须首先将其从外部 HashSet 中删除，然后重新添加(如有必要)。

(您并没有真正提供足够的代码来确定这是否真的是问题所在，但这是我最好的猜测)。

Set<Set<String>> outerSet = new HashSet<String>();
Set<String> innerSet = new HashSet<String>();

innerSet.add("foo");
outerSet.add(innerSet);

// *** BROKEN ***
innerSet.add("bar");       // <- adding element to innerSet changes result of innerSet.hashCode()
outerSet.remove(innerSet); // <- this may or may not work because outerSet is _broken_
// *** BROKEN ***

// *** CORRECT ***
outerSet.remove(innerSet);
innerSet.add("bar");
// now you can put innerSet back in outerSet if necessary