Java集合API HashSet删除方法

我在使用Java Collections API时遇到此问题。基本上这是一个实现Kruskal算法寻找MST的支持方法。我创建了这个类来实现union/find算法。Java集合API HashSet删除方法

我的问题，因为我能找到解决办法，是否有人知道为什么“联合”方法中的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;

来源

2011-04-21 oscarcollings

@lwburk感谢您的格式帮助，赞赏。 – oscarcollings 2011-04-21 21:39:21

问题取代它的是，当你修改嵌套HashSets的内容之一，你搞砸了外部HashSet的内部（因为嵌套的hashCode（）编辑HashSet已更改）。为了正确维护这个集合，每当你想修改其中一个嵌套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

来源

2011-04-21 03:16:07 jtahlborn

因此要清楚修改HashSet类的对象的内容还会修改该类的hashCode（）方法？我只是想澄清你的答案，因为你似乎说你必须从外部HashSet中移除它。你的意思是基础？或者你的意思是包含该对象的基础子集？（直觉上我会认为这是内在的）。我只是对您指定的删除顺序稍有困惑。想知道更多，并感谢回答。 – oscarcollings 2011-04-21 21:42:26

@oscarcollings - 对不起，随着所有的游戏集合在一起，很难澄清我在说什么。我会添加一些代码示例。 – jtahlborn 2011-04-22 11:01:25

哦，是的，这是有道理的。我现在看到，为了保持散列函数的完整性，你必须采取内部设置。感谢您的帮助，这个例子确实有助于澄清事情。 – oscarcollings 2011-04-23 02:38:33

上@ 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

一个理由添加到列表中尽量使用一成不变的馆藏尽可能。

来源

2011-04-21 03:47:54 andersoj

Java集合API HashSet删除方法

回答

相关问题