Java Collections API HashSet 删除方法

Question

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

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

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

我想知道是否有人能看到错误。另外我应该注意，我从不同的类调用它，但是，调用是使用使用 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

Answer 2

跟进@jtahlborn的回答，AbstractSet.hashCode() 说

返回此值的哈希码值
放。定义集合的哈希码
是哈希码的总和
集合中的元素。这确保了
s1.equals(s2) 意味着
s1.hashCode()==s2.hashCode() 对于任何
两组 s1 和 s2，根据要求
Object.hashCode通用合约。

这个实现枚举了
集合，调用hashCode方法
在集合中的每个元素上，以及
将结果相加。

演示 @jtahlborn 答案（正确）的代码

import java.util.HashSet;
import java.util.Set;


public class TestHashSetHashCode {

  public static void main(String[] args)
  {
    Set<String> strings = new HashSet<String>();
    strings.add("one");
    strings.add("two");
    strings.add("three");
    strings.add("four");
    strings.add("five");
    Set<String> test = new HashSet<String>();
    System.out.println("Code "+test.hashCode());
    for (String s : strings) {
      test.add(s);
      System.out.println("Code "+test.hashCode());
    }
  }
}

输出

Code 0
Code 115276
Code 3258622
Code 3368804
Code 113708290
Code 116857384

添加到列表中以尽可能使用不可变集合的又一个原因。