元素存在但 `Set.contains(element)` returns false

Question

一个元素如何不包含在原始集合中但包含在其未修改副本中？

原始集不包含该元素，而其副本包含该元素。 See image.

下面的方法 returns true，虽然它应该总是 return false。 c 和 clusters 的实现在这两种情况下都是 HashSet。

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

调试显示元素是包含在原来的，但是由于某些原因Set.contains(element) returns false。 See image.

有人能给我解释一下这是怎么回事吗？

Answer 1

最常见的原因是元素或键在插入后被更改，导致底层数据结构损坏。

注意：当您将对 Set<String> 的引用添加到另一个 Set<Set<String>> 时，您正在添加引用的副本，底层 Set<String> 不会被复制，如果您更改它，这些更改会影响您放入的 Set<Set<String>>。

例如

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 2

如果您更改 Set 中的元素（在您的情况下，元素是 Set<String>，因此添加或删除字符串会更改它们），Set.contains(element) 可能无法定位它，因为元素的 hashCode 将不同于元素首次添加到 HashSet 时的内容。

当您创建一个包含原始元素的新 HashSet 时，这些元素将根据其当前 hashCode 添加，因此 Set.contains(element) 将 return 为真对于新 HashSet.

您应该避免将可变实例放在 HashSet 中（或将它们用作 HashMap 中的键），如果无法避免，请确保在删除之前删除元素改变它并在之后重新添加它。否则你的HashSet会坏掉的。

一个例子：

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 3

如果主要 Set 是 TreeSet（或者可能是其他 NavigableSet），那么如果您的对象比较不完美，则有可能发生这种情况。

关键是HashSet.contains看起来像：

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

和map是一个HashMap和HashMap.containsKey看起来像：

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

因此它使用密钥的 hashCode 来检查是否存在。

A TreeSet 但是在内部使用 TreeMap 并且它的 containsKey 看起来像：

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

因此它使用 Comparator 来查找密钥。

因此，总而言之，如果您的 hashCode 方法与您的 Comparator.compareTo 方法不一致（比如说 compareTo returns 1 而 hashCode returns 不同的值）然后你会看到这种模糊的行为。

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);
}

打印

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}]

所以即使对象是在 TreeSet 中它也没有找到它，因为比较器从来没有 returns 0。但是，一旦它在 HashSet 中，一切都很好，因为 HashSet 使用 hashCode 找到它并且它们以有效的方式运行。

元素存在但 `Set.contains(element)` returns false

Element is present but `Set.contains(element)` returns false

java

hash

contains

set

hashset