java - HashSet<List<T>> 中的唯一条目，其中列表可能包含空条目

Question

有一个List<MyElement> = new ArrayList<MyElement>();

class MyElement {
  private Object[] values;
  //...
}

我需要在此列表中找到所有唯一的条目。我会用 HashSet , 但问题是 values可能包含 null AND 应该假定 null等于任何其他值。例如，Object[] o1 = new Object[]{1,null,"s2"}和 Object[] o2 = new Object[]{1,2,"s2"}应该被认为是相同的条目(即非唯一的)，并且只有其中一个应该保留在 HashSet 中。 .有什么方法可以覆盖 HashSet 中的适当函数吗？

Answer 1

add() 和 contains() 真的需要 O(1) 时间吗？我找不到为 MyElement 类编写满足您要求的 hashCode() 函数的好方法。

然而，比较器(或使 MyElement 可比较)可以解决问题，然后您可以使用 TreeSet 找出列表中的独特元素。

这是第一次尝试(你不应该按原样使用它，它可能不会工作)。

class MyElementComparator implements Comparator<MyElement> {
    @Override
    public int compare(MyElement e, MyElement f) {
        int sizeCmp = e.values.length - f.values.length;

        if(sizeCmp != 0) // Lists are of different sizes, elements aren't equal
            return sizeCmp; 

        // Start comparing element by element
        for(int i=0; i<e.values.length; i++) {
            Object eo = e.values[i];
            Object fo = f.values[i];

            // Null is a wildcard
            if(eo == null || fo == null)
                continue;

            // If objects are the same, then continue too.
            if(eo == fo || eo.equals(fo))
                continue;

            // Otherwise, decide on one object or the other based on hashcode (or any other valid mean).
                return eo.hashCode() - fo.hashCode();
        }

        // All elements were equal or skipped, then the objects are equal.
        return 0;
    }
}

快速测试似乎表明它有效:

    MyElement a = new MyElement(1, null, "s2");
    MyElement b = new MyElement(1, 2, "s2");
    MyElement c = new MyElement(null, "s", 3);

    TreeSet<MyElement> set = new TreeSet<MyElement>(new MyElementComparator());
    set.add(a);
    set.add(b);
    set.add(c);
    System.out.println(set.size()); // 2

但是，如果您向集合中添加一个与另外两个不同元素相等的元素，事情就会失败。例如 {1} 和 {2} 是不同的，但是如果您添加 {null}，则该集合应该减少为 {null}，并且不会发生这种情况。

没有 Comparator 可以做到这一点，您将需要另一个数据结构，也许是一个不相交的集合(Union Find)？ http://en.wikipedia.org/wiki/Disjoint-set_data_structure