1

我正在学习数据结构和算法，并尝试在 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 个或更多元素，集合会正确合并，但即使在调用之后 set2 也不会从集合集合中删除allsets.remove(set2)

但是，如果要合并的集合，即；set2，只有 1 个元素，allSets.remove(set2)成功从集合集合中移除 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带有多个元素的 a，但成功地删除了LinkedHashSet带有 1 个元素的 a。

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

4

2 回答 2

4

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

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

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

例子：

  1. 创建一个包含 1 的 LinkedHashSet inner1。hashCode 为 5
  2. 将其存储在 outerSet 中
  3. outerSet 将 inner1 存储在桶 5 中，因为它的 hashCode 为 5
  4. 将 2 添加到 inner1。现在它的 hashCode 变为 3。
  5. 从外部集合中移除 inner1。
  6. outerSet 获取 inner1 的 hashCode 以找到存储 inner1 的桶：3
  7. outerSet 尝试在存储桶 3 中查找 inner1。什么也没找到，因为它存储在存储桶 5 中。

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

于 2015-12-24T14:49:26.367 回答
0

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

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

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

}

于 2015-12-24T15:57:42.047 回答