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

鉴于MyClass的List一个对象（如果需要定制Comparitor myComparitor），有什么好的选择是有检查，如果List包含两个“平等”的对象？的Java：测试集合中的重复的对象

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

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

我最初的想法是创建各种各样的哈希表，但我怀疑有来完成同样的事情非黑客方式：

SortedSet mySet = new TreeSet(myComparitor);
mySet.addAll(myList);
// Find duplicates in a sorted set in O(N) time

附： Markdown有没有很好的参考？

来源

2010-08-25 Daniel

[Java：检测ArrayList中的重复项？]可能的重复项（http://stackoverflow.com/questions/562894/java-detect-duplicates-in-arraylist） – krock 2010-08-25 23:54:43

你需要知道哪些项目是重复的或做你只需要知道是否有重复？ – mnuzzo 2010-08-25 23:55:45

“平等的对象”是什么意思？如果从Object继承的equals（）方法不够重写是你唯一的选择。 – 2010-08-25 23:56:09

如果元素的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可能表现更好的唯一情况是何时可能没有重复。

来源

2010-08-26 00:15:46

谢谢，这是一个好点 - 我可以创建列表的副本，并简单地对其进行排序。我可能会采用这种方法。（而另一好点 - 我可以创建通过手动生成的哈希值键控一个TreeMap。）感谢约'Set.addAll性能尖端（）'。我正在重写'O（N^2）'中执行的代码，我认为'O（NlogN）'应该是可以接受的（如果比例常数很低）。 – Daniel 2010-08-27 13:14:59

如果你已经有排序的列表，你可以看看任何元素和下一个元素，如果他们是相同的，你有dups。

在你的问题中，你正在使用一个TreeSet，它已经清除了重复项，所以如果你只需要知道你是否有重复项，请检查mySet的大小和myList的大小。如果他们不一样，你有dups。

来源

2010-08-26 00:20:07

谢谢，我已经编辑了上面的帖子来澄清问题。（你是对的，在一个排序列表中查找重复项很简单，如果我创建一个包装类覆盖Object.equals（），TreeSet会自动去重复，但是这样做会涉及开销。） – Daniel 2010-08-27 13:07:29

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

回答

相关问题