LinkedHashSets的HashSet不删除具有多个元素的LinkedHashSet

Question

我正在学习数据结构和算法，并尝试在 Java 中实现不相交集数据结构。这是我执行相同操作的代码-

import java.util.*;

public class DisjointSet<T> {
    Set<LinkedHashSet<T>> allSets;

    DisjointSet()   {
        allSets = new HashSet<LinkedHashSet<T>>();
    }

    public void makeSet(T t)    {
        Iterator itr = allSets.iterator();
        while (itr.hasNext())   {
            LinkedHashSet set = (LinkedHashSet) itr.next();
            if (set.contains(t))    {
                return;
            }
        }

        LinkedHashSet<T> set = new LinkedHashSet<T>();
        set.add(t);

        allSets.add(set);
    }

    public T findSet(T t)   {       
        Iterator itr = allSets.iterator();
        while (itr.hasNext())   {
            LinkedHashSet set = (LinkedHashSet) itr.next();
            if (set.contains(t))    {
                Iterator itr1 = set.iterator();
                T t1 = (T) itr1.next();
                return t1;
            }
        }

        return null;
    }

    public void union(T t1, T t2)   {
        LinkedHashSet<T> set1 = null, set2 = null;

        Iterator itr = allSets.iterator();
        while (itr.hasNext())   {
            LinkedHashSet set = (LinkedHashSet) itr.next();
            if (set.contains(t1))   {
                set1 = (LinkedHashSet<T>) set;
                System.out.println("Got set1:: " + set1);
            } else if (set.contains(t2))    {
                set2 = (LinkedHashSet<T>) set;
                System.out.println("Got set2:: " + set2);
            }
        }

        if (null != set1)   {
            System.out.println("Adding set2 to set1");
            set1.addAll(set2);

            if (null != set2)   {
                System.out.println("Removing set2");
                System.out.println(allSets.remove(set2));
            }
        }
    }

    public void viewAllSets()   {
        System.out.println(this.allSets);
    }
}

这是我正在运行测试我的实现的代码-

public class DisjointTest   {   
    public static void main(String [] args) {
        DisjointSet<Integer> dsets = new DisjointSet<Integer>();

        dsets.makeSet(30);
        dsets.makeSet(600);
        dsets.makeSet(20);
        dsets.makeSet(25);
        dsets.makeSet(90);
        dsets.makeSet(100);
        dsets.makeSet(1);

        dsets.viewAllSets();
        System.out.println();

        System.out.println(dsets.findSet(25));

        dsets.union(20, 25);
        dsets.viewAllSets();

        System.out.println();

        System.out.println(dsets.findSet(25));

        dsets.union(1, 100);
        dsets.viewAllSets();

        System.out.println();

        dsets.union(20, 100);
        dsets.viewAllSets();

        System.out.println(dsets.findSet(100));

        System.out.println();

        dsets.union(30, 90);
        dsets.viewAllSets();

        System.out.println();

        dsets.union(1, 90);
        dsets.viewAllSets();
    }   
}

当我尝试将一个集合与另一个集合合并时，比如 set2，它有 2 个或更多元素，这些集合被正确合并，但即使在调用 allsets.remove(set2)

但是，如果要合并集合，即； set2，只有 1 个元素，allSets.remove(set2) 成功从 sets 集合中删除 set2。

这是我的代码输出，它证实了我的问题-

[[1], [100], [20], [25], [600], [90], [30]]

25
Got set1:: [20]
Got set2:: [25]
Adding set2 to set1
Removing set2
true
[[1], [100], [20, 25], [600], [90], [30]]

20
Got set1:: [1]
Got set2:: [100]
Adding set2 to set1
Removing set2
true
[[1, 100], [20, 25], [600], [90], [30]]

Got set2:: [1, 100]
Got set1:: [20, 25]
Adding set2 to set1
Removing set2
false
[[1, 100], [20, 25, 1, 100], [600], [90], [30]]
1

Got set1:: [20, 25, 1, 100]
Got set2:: [90]
Adding set2 to set1
Removing set2
true
[[1, 100], [20, 25, 1, 100, 90], [600], [30]]

我无法理解为什么 HashSet.remove(LinkedHashSet) 无法删除包含多个元素的 LinkedHashSet，但成功删除包含 1 个元素的 LinkedHashSet。

我们将不胜感激任何帮助。非常感谢。

Answer 1

您错过了使用集合的一个关键点：您存储在集合中的值不得修改（至少不能以改变其相等性的方式）。

如果您修改存储在 HashSet 中的值，并且该修改更改了值的 hashCode，则无法再在集合中找到该值，因为它不在与其 hashCode 对应的存储桶中没有了。

当一个set与另一个set合并时，你改变了它的hashCode，从而彻底破坏了整个数据结构的正确性。

示例：

创建一个包含1的LinkedHashSet inner1。hashCode为5
存放在outerSet中
outerSet 将 inner1 存储在 bucket 5 中，因为它的 hashCode 是 5
将 2 添加到 inner1。现在它的 hashCode 变成了 3.
从外部集中删除内部 1。
outerSet获取inner1的hashCode找到inner1所在的桶：3
outerSet 尝试在桶 3 中查找 inner1。什么也没找到，因为它存储在桶 5 中。

请注意，TreeSet 也是如此。 TreeSets 通过构建值树来工作：如果 A 小于根，则它转到左分支。如果你修改 A 并且它变得比根大，TreeSet 将尝试在树的错误分支中找到它。

Answer 2

至于其他人已经回答的理论基础。

就解决方案而言，使用良好的 ol 向量并避免花哨的 smanchy hashsets - 如果你使用 hashsets，你在数学上理解的集合的概念就会被破坏

import java.util.*;

public class DisjointSet<T> {
Vector allSets;

DisjointSet()   {
    allSets = new Vector();
}

public void makeSet(T t)    {
    Iterator itr = allSets.iterator();
    while (itr.hasNext())   {
        Vector set = (Vector) itr.next();
        if (set.contains(t))    {
            return;
        }
    }

    Vector set = new Vector();
    set.add(t);

    allSets.add(set);
}

public T findSet(T t)   {       
    Iterator itr = allSets.iterator();
    while (itr.hasNext())   {
        Vector set = (Vector) itr.next();
        if (set.contains(t))    {
            Iterator itr1 = set.iterator();
            T t1 = (T) itr1.next();
            return t1;
        }
    }

    return null;
}

public void union(T t1, T t2)   {
    Vector set1 = null, set2 = null;

    Iterator itr = allSets.iterator();
    while (itr.hasNext())   {
        try {
        Vector set = (Vector) itr.next();
        if (set.contains(t1))   {
            set1 = (Vector) set;
            System.out.println("Got set1:: " + set1);
        } else if (set.contains(t2))    {
            set2 = (Vector) set;
            System.out.println("Got set2:: " + set2);
        }
        }
        catch(Exception e) { e.printStackTrace(); }
    }

    if (null != set1)   {
        System.out.println("Adding set2 to set1");
        set1.addAll(set2);

        if (null != set2)   {
            System.out.println("Removing set2");
    viewAllSets();
            System.out.println(allSets.contains(set2)+" "+allSets.remove(set2));
        }
    }
}

public void viewAllSets()   {
    System.out.println(this.allSets);
}

public static void main(String [] args) {
    DisjointSet<Integer> dsets = new DisjointSet<Integer>();

    dsets.makeSet(30);
    dsets.makeSet(600);
    dsets.makeSet(20);
    dsets.makeSet(25);
    dsets.makeSet(90);
    dsets.makeSet(100);
    dsets.makeSet(1);

    dsets.viewAllSets();
    System.out.println();

    System.out.println(dsets.findSet(25));

    dsets.union(20, 25);
    dsets.viewAllSets();

    System.out.println();

    System.out.println(dsets.findSet(25));

    dsets.union(1, 100);
    dsets.viewAllSets();

    System.out.println();

    dsets.union(20, 100);
    dsets.viewAllSets();

    System.out.println(dsets.findSet(100));

    System.out.println();
}

}

LinkedHashSets的HashSet不删除具有多个元素的LinkedHashSet

HashSet of LinkedHashSets does not delete LinkedHashSet with multiple elements

java

collections

hashset

linkedhashset