What is the best way to remove duplicates in an Array in Java?

Question

I have an Array of Objects that need the duplicates removed/filtered. I was going to just override equals & hachCode on the Object elements, and then stick them in a Set... but I figured I should at least poll stackoverflow to see if there was another way, perhaps some clever method of some other API?

• LeppyR64: Why place yourself in this spot? Why not prevent the duplicates in the first place?
• erickson: Ask a question about removing duplicates... get a bunch of duplicate answers. The irony!
• OscarRyz: The way you're describing is perfect.

Answer 1

I would agree with your approach to override hashCode() and equals() and use something that implements Set.

Doing so also makes it absolutely clear to any other developers that the non-duplicate characteristic is required.

Another reason - you get to choose an implementation that meets your needs best now:

• HashSet
• TreeSet
• LinkedHashSet

and you don't have to change your code to change the implementation in the future.

Answer 2

I found this in the web

Here are two methods that allow you to remove duplicates in an ArrayList. removeDuplicate does not maintain the order where as removeDuplicateWithOrder maintains the order with some performance overhead.

1. The removeDuplicate Method:

   /** List order not maintained **/
   public static void removeDuplicate(ArrayList arlList)
   {
    HashSet h = new HashSet(arlList);
    arlList.clear();
    arlList.addAll(h);
   }
   

2. The removeDuplicateWithOrder Method:

   /** List order maintained **/
   public static void removeDuplicateWithOrder(ArrayList arlList)
   {
    Set set = new HashSet();
    List newList = new ArrayList();
    for (Iterator iter = arlList.iterator(); iter.hasNext();) {
    Object element = iter.next();
    if (set.add(element))
    newList.add(element);
    }
    arlList.clear();
    arlList.addAll(newList);
   }
   

• TravisO: Good answer, but your 2nd example isn't in a code format block
• Markus Lausberg: thanks to Ken G... i tried it a couple of times but i could ot fix the second code blog
• Daddy Warbox: LinkedHashSet keeps it in order. That may optimize it further.

Answer 3

Overriding equals and hashCode and creating a set was my first thought too. It's good practice to have some overridden version of these methods anyway in your inheritance hierarchy.

I think that if you use a LinkedHashSet you'll even preserve order of unique elements...

• Ken Gentle: Yep, LinkedHashSet will maintain the insertion order.
• McDowell: It is not good practise to override equals and hashCode "anyway", especially in any class that will sit in an inheritance hierarchy. See Effective Java (Bloch) for more.
• Dan Vinton: McDowell, I wan't really clear - I meant that there should be an overridden version somewhere in your inheritance hierarchy, and I've amended the answer to reflect that. I've not got a copy of Effective Java - is this what Bloch is getting at?

Answer 4

Basically, you want a LinkedHashSet<T> implementation that supports the List<T> interface for random access. Hence, this is what you need:

public class LinkedHashSetList<T> extends LinkedHashSet<T> implements List<T> {

// Implementations for List<T> methods here ...

}

The implementation of the List<T> methods would access and manipulate the underlying LinkedHashSet<T>. The trick is to have this class behave correctly when one attempts to add duplicates via the List<T> add methods (throwing an exception or re-adding the item at a different index would be options: which you can either choose one of or make configurable by users of the class).

Answer 5

Use a List distinctList to record element at the first time iterator stumble into it, returns the distinctList as list removed all duplicates

 private List removeDups(List list) {
 Set tempSet = new HashSet();
 List distinctList = new ArrayList();
 for(Iterator it = list.iterator(); it.hasNext();) {
 Object next = it.next();
 if(tempSet.add(next)) {
 distinctList.add(next);
 } 
 }
 return distinctList;
 } 

• Filip Luchianenco: the complexity is very high, since List.contains has a O(n) time complexity, thus the complexity is O(N^2)
• didxga: @FilipLuchianenco you are right, I have updated my implementation
• Filip Luchianenco: Then you only need to keep adding the new value, if it exists it will just return false. As a result, you'll end up with an iterator and a Set to which you keep adding unique values. The only downside is the order as Set does not keep it due to resizing. Then the other solution is to have a list and a set, and if your set.add(object) returns true, you add it to the new list as well; then return the list.
• didxga: Why do we need to care about the order of the Set, since what we are going to change is the List passed in the function, which we use iterator to remove duplicate, which doesn't change the internal order of the List
• Filip Luchianenco: well, removing an item from a List is a very inefficient, since List.remove() will have to create a new list and copy all elements every time, so your complexity now is O(n^k) where k is the list size. So I did not even want to consider that as an option.

Answer 6

I'd like to reiterate the point made by Jason in the comments:

Why place yourself at that point at all?

Why use an array for a data structure that shouldn't hold duplicates at all?

Use a Set or a SortedSet (when the elements have a natural order as well) at all times to hold the elements. If you need to keep the insertion order, then you can use the LinkedHashSet as it has been pointed out.

Having to post-process some data structure is often a hint that you should have choosen a different one to begin with.

• Liggy: I agree with all comments about the concerns of the initial data structure being an Array. I am trying to lobby the developer to refactor to a Set. Thanks all for your feedback and wisdom!

Answer 7

Of course the original post begs the question, "How did you get that array (that might contain duplicated entries) in the first place?"

Do you need the array (with duplicates) for other purposes, or could you simply use a Set from the beginning?

Alternately, if you need to know the number of occurrences of each value, you could use a Map<CustomObject, Integer> to track counts. Also, the Google Collections definition of the Multimap classes may be of use.

Answer 8

A Set is definitely your best bet. The only way to remove things from an array (without creating a new one) is to null them out, and then you end up with a lot of null-checks later.

Answer 9

Speaking from a general programming standard you could always double enumerate the collections then the compare the source and target.

And if your inner enumeration always starts one entry after the source, it's fairly efficient (pseudo code to follow)

foreach ( array as source )
{
 // keep track where we are in the array
 place++;
 // loop the array starting at the entry AFTER the current one we are comparing to
 for ( i=place+1; i < max(array); i++ )
 {
 if ( source === array[place] )
 {
 destroy(array[i]);
 }
 }
}

You could arguably add a break; statement after the destroy but then you only discover the first duplicate, but if that's all you will ever have, then it would be a nice small optimization.