的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：測試集合中的重複的對象

回答

相關問題