Java Collections API HashSet 제거 방법

Question

Java Collections API로 작업하는 동안이 문제점이 발생했습니다. 기본적으로 이것은 MST를 찾는 Kruskal의 알고리즘 구현을위한 지원 방법입니다. union/find 알고리즘을 구현하기 위해이 클래스를 만들었습니다.

제 질문은 작업을 찾을 수 있었기 때문에 "union"메서드의 remove 메서드가 일관되게 작동하지 않는 이유에 대해 알 수 있습니다. 그것은 런타임에 일부 요소를 제거하고 다른 요소는 제거하지 않습니다. 예를 들어, 도시와 관련된 작업에 이것을 구현했는데 일부 도시를 제거하는 것이 싫은 것처럼 보였습니다. 특히 그것은 두 세트의 다른 세트를 반복적으로 우연히 발견했지만 항상 동일한 세트를 발견했습니다. 나는 이것이 객체 참조 문제인지 여부, 즉 내가 잘못된 것을 테스트하고 있는지의 여부를 궁금해했다. 그러나 나는 그 문제를 해결할 수 없었다.

저는 요소를 제거한 루프로 대체 할 수 있었고 알고리즘이 완벽하게 실행되었으므로 나머지 작업이 정확하다는 것을 알고 있습니다. 아마 약간 더 나쁜 성능으로.

누구든지 실수를 볼 수 있는지 궁금합니다. 또한 나는 다른 클래스에서 호출했음을 주목해야한다. 그러나 호출은 find 메소드를 사용하여 검색된 요소로 이루어진다. remove 메소드를 변경하는 것만으로 모든 것이 작동하도록 find 메소드가 제대로 작동해야합니다. 즉, 적절한 객체를 찾고 반환하는 것이기 때문에 잘 작동해야합니다.

감사

오스카

/* 
* 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

문제로 대체 당신이 중첩 된 HashSets 중 하나의 내용을 수정할 때, 당신은 바깥 쪽 HashSet의 내부 구조를 망친다. 왜냐하면 네스트의 hashCode() ed 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 

Answer 2

@ jtahlborn의 대답에 후속 조치, AbstractSet.hashCode()에 대한 계약은

이 세트의 해시 코드 값을 돌려 말했다. 집합의 해시 코드는 으로 집합의 요소의 해시 코드 합계로 정의됩니다. 따라서 s1.equals (s2)는 s1.hashCode() == s2.hashCode()에 대해 두 세트 s1 및 s2를 의미하며, 이는 Object.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 

또 하나의 이유를 설명합니다.