Yếu tố hiện diện nhưng 'Set.contains (yếu tố) `trả về false

Question

Làm thế nào có thể một yếu tố không được chứa trong các bộ hồ sơ gốc nhưng trong chưa sửa đổi bản sao của nó?

Tập hợp ban đầu không chứa phần tử trong khi bản sao của nó. See image.

Phương thức sau đây trả về true, mặc dù nó luôn trả về false. Việc triển khai c và clusters là trong cả hai trường hợp HashSet.

public static boolean confumbled(Set<String> c, Set<Set<String>> clusters) { 
    return (!clusters.contains(c) && new HashSet<>(clusters).contains(c)); 
} 

Debugging đã chỉ ra rằng các yếu tố là chứa trong bản gốc, nhưng Set.contains(element) lợi nhuận false đối với một số lý do. See image.

Ai đó có thể giải thích cho tôi điều gì đang xảy ra?

Answer 1

Nếu bạn thay đổi một phần tử trong Set (trong trường hợp của bạn các yếu tố này là Set<String>, vì vậy thêm hoặc loại bỏ một String sẽ thay đổi chúng), Set.contains(element) có thể thất bại trong việc xác định vị trí nó, kể từ khi hashCode của nguyên tố này sẽ khác với yếu tố khi phần tử được thêm lần đầu tiên vào HashSet.

Khi bạn tạo một mới HashSet chứa các yếu tố của một bản gốc, các yếu tố được thêm vào dựa trên hiện hashCode họ, do đó Set.contains(element) sẽ trở thành sự thật cho cái mới HashSet.

Bạn nên tránh đặt các trường hợp có thể thay đổi trong HashSet (hoặc sử dụng chúng dưới dạng khóa trong HashMap) và nếu bạn không thể tránh nó, hãy đảm bảo bạn xóa phần tử đó trước khi bạn thay đổi nó và thêm lại sau đó. Nếu không, HashSet của bạn sẽ bị hỏng.

Một ví dụ:

Set<String> set = new HashSet<String>(); 
set.add("one"); 
set.add("two"); 
Set<Set<String>> setOfSets = new HashSet<Set<String>>(); 
setOfSets.add(set); 
boolean found = setOfSets.contains(set); // returns true 
set.add("three"); 
Set<Set<String>> newSetOfSets = new HashSet<Set<String>>(setOfSets); 
found = setOfSets.contains(set); // returns false 
found = newSetOfSets.contains(set); // returns true 

Answer 2

Lý do phổ biến nhất cho điều này là phần tử hoặc khóa đã bị thay đổi sau khi chèn dẫn đến tham nhũng cấu trúc dữ liệu cơ bản.

lưu ý: khi bạn thêm một tham chiếu đến một Set<String> khác Set<Set<String>> bạn đang thêm một bản sao của tham khảo, các Set<String> cơ bản không được sao chép và nếu bạn thay đổi nó những thay đổi này ảnh hưởng đến Set<Set<String>> bạn đặt nó vào.

ví dụ:

Set<String> s = new HashSet<>(); 
Set<Set<String>> ss = new HashSet<>(); 
ss.add(s); 
assert ss.contains(s); 

// altering the set after adding it corrupts the HashSet 
s.add("Hi"); 
// there is a small chance it may still find it. 
assert !ss.contains(s); 

// build a correct structure by copying it. 
Set<Set<String>> ss2 = new HashSet<>(ss); 
assert ss2.contains(s); 

s.add("There"); 
// not again. 
assert !ss2.contains(s); 

Answer 3

Nếu chính Set là một TreeSet (hoặc có lẽ một số khác NavigableSet) sau đó nó là có thể, nếu đối tượng của bạn đang không hoàn hảo so sánh, cho điều này xảy ra.

Điểm quan trọng là HashSet.contains trông giống như:

public boolean contains(Object o) { 
    return map.containsKey(o); 
} 

và map là một HashMap và HashMap.containsKey trông giống như:

public boolean containsKey(Object key) { 
    return getNode(hash(key), key) != null; 
} 

nên nó sử dụng hashCode của khóa để kiểm tra sự hiện diện.

Một TreeSet tuy nhiên sử dụng một TreeMap nội bộ và nó containsKey trông giống như:

final Entry<K,V> getEntry(Object key) { 
    // Offload comparator-based version for sake of performance 
    if (comparator != null) 
     return getEntryUsingComparator(key); 
    ... 

Vì vậy, nó sử dụng một Comparator để tìm chìa khóa.

Vì vậy, trong Tóm lại, nếu phương pháp hashCode bạn không đồng ý với phương pháp Comparator.compareTo của bạn (nói compareTo lợi nhuận 1 khi hashCode lợi nhuận giá trị khác nhau) sau đó bạn sẽ thấy loại hành vi hèn hạ đâu.

class BadThing { 

    final int hash; 

    public BadThing(int hash) { 
     this.hash = hash; 
    } 

    @Override 
    public int hashCode() { 
     return hash; 
    } 

    @Override 
    public String toString() { 
     return "BadThing{" + "hash=" + hash + '}'; 
    } 

} 

public void test() { 
    Set<BadThing> primarySet = new TreeSet<>(new Comparator<BadThing>() { 

     @Override 
     public int compare(BadThing o1, BadThing o2) { 
      return 1; 
     } 
    }); 
    // Make the things. 
    BadThing bt1 = new BadThing(1); 
    primarySet.add(bt1); 
    BadThing bt2 = new BadThing(2); 
    primarySet.add(bt2); 
    // Make the secondary set. 
    Set<BadThing> secondarySet = new HashSet<>(primarySet); 
    // Have a poke around. 
    test(primarySet, bt1); 
    test(primarySet, bt2); 
    test(secondarySet, bt1); 
    test(secondarySet, bt2); 
} 

private void test(Set<BadThing> set, BadThing thing) { 
    System.out.println(thing + " " + (set.contains(thing) ? "is" : "NOT") + " in <" + set.getClass().getSimpleName() + ">" + set); 
} 

in

BadThing{hash=1} NOT in <TreeSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=2} NOT in <TreeSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=1} is in <HashSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=2} is in <HashSet>[BadThing{hash=1}, BadThing{hash=2}] 

nên mặc dù các đối tượng là trong TreeSet nó không phải là tìm nó bởi vì so sánh không bao giờ trả 0. Tuy nhiên, một khi nó ở trong HashSet tất cả là tốt bởi vì HashSet sử dụng hashCode để tìm nó và chúng hoạt động một cách hợp lệ.