Java:测试集合中的重复对象

Question

给定 MyClass 对象的 List(如果需要，还有一个自定义的 Comparitor myComparitor)，有哪些好的选项可以检查 code>List 包含两个“相等”的对象？

编辑:如果有重复项，返回对一个或多个重复项的引用。

在这种情况下重写 MyClass.equals(MyClass) 不是一个选项。

我最初的想法是创建一个哈希表，但我怀疑有一种非黑客方法可以完成同样的事情:

SortedSet mySet = new TreeSet(myComparitor);
mySet.addAll(myList);
//在 O(N) 时间内在有序集合中查找重复项

附言有没有关于 Markdown 的好引用？

Answer 1

如果元素的 equals(Object) 方法没有提供您需要的语义，则 HashMap 或 HashSet 不是选项。您的选择是:

• 使用 TreeMap 进行重复数据删除。这是 O(NlogN)。
• 对 ArrayList 或副本进行排序，然后遍历查找元素 i 等于元素 i + 1。这是 O(NlogN)。
• 找到哈希集的替代实现方式，它允许您提供单独的对象来实现相等性和哈希。 (Apache 或 Google 集合都不支持此功能，因此您需要看得更远。)
• 为您的元素类型创建一个包装类，覆盖 equals(Object) 和 hashCode()，并使用 HashSet 进行重复数据删除包裹的物体。这是 O(N)，但由于创建了包装对象，比例常数将大于简单的 HashSet。

当使用 Set 进行重复数据删除时，最好使用循环而不是 addAll。如果您需要知道所有重复项是什么，这是必要的。如果您不需要知道这一点，那么使用循环可以让您在找到第一个重复项时停止。 addAll 可能表现更好的唯一情况是可能没有重复项。