단순히 세트가 동일한 지 알고 싶다면 equalson 메서드 AbstractSet는 대략 다음과 같이 구현됩니다.

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return containsAll(c);
    }

다음과 같은 일반적인 경우를 어떻게 최적화하는지 확인하십시오.

• 두 개체는 동일합니다
• 다른 개체는 전혀 집합이 아닙니다.
• 두 세트의 크기가 다릅니다.

그 후, 이 세트에도없는 다른 세트의 요소를 찾으면 즉시 containsAll(...)리턴 false합니다. 그러나 모든 요소가 두 세트에 모두 존재하는 경우 모든 요소를 ​​테스트해야합니다.

따라서 최악의 성능은 두 세트가 동일하지만 동일한 객체가 아닐 때 발생합니다. 그 비용은 일반적으로 O(N)또는 O(NlogN)의 구현에 따라 this.containsAll(c).

세트가 크고 요소의 비율이 아주 조금만 다를 경우 최악에 가까운 성능을 얻을 수 있습니다.

최신 정보

사용자 지정 집합 구현에 시간을 투자하려는 경우 “거의 동일한”사례를 개선 할 수있는 접근 방식이 있습니다.

아이디어는 .NET에서 세트의 현재 해시 코드 값을 가져올 수 있도록 전체 세트에 대한 해시를 미리 계산하고 캐시해야한다는 것입니다 O(1). 그런 다음 두 세트의 해시 코드를 가속도로 비교할 수 있습니다.

그런 해시 코드를 어떻게 구현할 수 있습니까? 설정된 해시 코드가 다음과 같으면

• 빈 세트의 경우 0
• 비어 있지 않은 세트에 대한 모든 요소 해시 코드의 XOR,

그런 다음 요소를 추가하거나 제거 할 때마다 세트의 캐시 된 해시 코드를 저렴하게 업데이트 할 수 있습니다. 두 경우 모두 현재 설정된 해시 코드로 요소의 해시 코드를 XOR하기 만하면됩니다.

물론 이것은 요소 해시 코드가 안정적이고 요소가 집합의 구성원이라고 가정합니다. 또한 요소 클래스 해시 코드 함수가 좋은 확산을 제공한다고 가정합니다. 두 세트의 해시 코드가 동일 할 O(N)때 모든 요소 의 비교로 돌아 가야하기 때문 입니다.

적어도 이론 상으로는이 아이디어를 조금 더 발전시킬 수 있습니다.

경고 -이것은 매우 추측 적입니다. 당신이 원한다면 “생각 실험”.

set 요소 클래스에 요소에 대한 암호화 체크섬을 반환하는 메서드가 있다고 가정합니다. 이제 요소에 대해 리턴 된 체크섬을 XOR하여 세트의 체크섬을 구현하십시오.

이것이 우리에게 무엇을 사나요?

음, 아무 일도 일어나지 않는다고 가정하면 두 개의 같지 않은 집합 요소가 동일한 N 비트 체크섬을 가질 확률은 2 ^-N 입니다. 그리고 2 개의 같지 않은 세트가 동일한 N 비트 체크섬을 가질 확률도 2 ^-N 입니다. 그래서 내 생각은 다음 equals과 같이 구현할 수 있다는 것입니다 .

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return checksums.equals(c.checksums);
    }

위의 가정 하에서 이것은 2 ^-N 시간에 한 번만 잘못된 답을 제공합니다 . N을 충분히 크게 만들면 (예 : 512 비트) 오답의 가능성은 무시할 수 있습니다 (예 : 대략 10 ^-150 ).

단점은 요소에 대한 암호화 체크섬을 계산하는 데 특히 비트 수가 증가함에 따라 매우 비싸다는 것입니다. 따라서 체크섬을 메모하기위한 효과적인 메커니즘이 정말로 필요합니다. 그리고 그것은 문제가 될 수 있습니다.

또 다른 단점은 확률이 아무리 작아도 0이 아닌 오류 확률은 허용되지 않을 수 있다는 것 입니다. (하지만 그렇다면 … 우주 광선이 임계 비트를 뒤집는 경우를 어떻게 처리합니까? 아니면 중복 시스템의 두 인스턴스에서 동일한 비트를 동시에 뒤집는 경우 어떻게합니까?)

답변

public static <E>  boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}

public static boolean equals(Set<?> set1, Set<?> set2){

    if(set1 == null || set2 ==null){
        return false;
    }

    if(set1.size() != set2.size()){
        return false;
    }

    return set1.containsAll(set2);
}

public static boolean equals(Set<?> set1, Set<?> set2){

  return set1 != null
    && set2 != null
    && set1.size() == set2.size()
    && set1.containsAll(set2);
}

    public class SortedSetComparitor <Foo extends Comparable<Foo>>
            implements Comparator<SortedSet<Foo>> {

        @Override
        public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
            Iterator<Foo> otherRecords = arg1.iterator();
            for (Foo thisRecord : arg0) {
                // Shorter sets sort first.
                if (!otherRecords.hasNext()) return 1;
                int comparison = thisRecord.compareTo(otherRecords.next());
                if (comparison != 0) return comparison;
            }
            // Shorter sets sort first
            if (otherRecords.hasNext()) return -1;
            else return 0;
        }
    }

        SetView<Record> added = Sets.difference(secondSet, firstSet);
        SetView<Record> removed = Sets.difference(firstSet, secondSet);

HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size());
int i = 0;
for(Record secondRecord : secondSet){
    hm.put(i,secondRecord);
    i++;
}
for(Record firstRecord : firstSet){
    for(int i=0; i<secondSet.size(); i++){
    //use hm for comparison
    }
}