Delete duplicates from an ArrayList using compareTo

Question

I'm trying to make an ArrayList of objects Edge, without any duplicates :

public class Edge implements Comparable<Edge>{
    private int vertex1, vertex2;
    //constructor, getter ...
    @Override
    public int compareTo(Edge o) {
        if (vertex1 == o.getVertex1() && vertex2 == o.getVertex2()) return 0;
        return 1;
    }
}

I thought that using a HashSet who doesn't accept duplicates will work but I was wrong :

ArrayList<Edge> edges = new ArrayList<Edge>();
//fill list (with possible duplicates)

//delete duplicates
Set<Edge> hs = new HashSet<Edge>();
hs.addAll(edges);
edges.clear();
edges.addAll(hs);

This method works with ArrayList of String, Integer, but I don't understand why it doesn't works for this case.

Sorry for my english, I'm french.

Possible duplicate of [Why do I need to override the equals and hashCode methods in Java?](https://stackoverflow.com/questions/2265503/why-do-i-need-to-override-the-equals-and-hashcode-methods-in-java) — AxelH, May 04 '18 at 08:13

score 4 · Answer 1 · answered May 04 '18 at 08:13

You have two options:

override equals() and hashcode() if you want to use a HashSet, or
use a TreeSet which relies on compareTo to determine the presence of duplicates.

So in your code, just replace Set<Edge> hs = new HashSet<Edge>(); with:

Set<Edge> hs = new TreeSet<Edge>();

and it will work as expected. Note that the fact that your compareTo is not consistent with equals may create other issues, so only do this if you understand what you are doing. More info in the javadoc of Comparable and TreeSet.

score 0 · Answer 2 · answered May 04 '18 at 08:11

0

Your objects has different hash so HashSet put it in different brackets.

When you override equals you should override hashCode too.

Equal objects must have same hash

answered May 04 '18 at 08:11

Mạnh Quyết Nguyễn

17,677
1
23
51

score 0 · Answer 3 · answered May 04 '18 at 08:15

Override hashCode and equals method

public class Edge implements Comparable<Edge>{
    private int vertex1, vertex2;
    //constructor, getter ...
    @Override
    public int compareTo(Edge o) {
        if (vertex1 == o.getVertex1() && vertex2 == o.getVertex2()) return 0;
        return 1;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + vertex1;
        result = prime * result + vertex2;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Edge other = (Edge) obj;
        if (vertex1 != other.vertex1)
            return false;
        if (vertex2 != other.vertex2)
            return false;
        return true;
    }
}

score 0 · Answer 4 · answered May 04 '18 at 09:25

0

What about this one :

public List<Edge> removeDuplicates(List<Edge> fullList) {

    List<Edge> noDuplicates = new ArrayList<>();

    for (Edge edge : fullList){
        if (!fullList.contains(edge))
            noDuplicates.add(edge);
    }

    return noDuplicates;
}

For me work fine to remove duplicates objects from a list!

answered May 04 '18 at 09:25

librushi

81
2
6

(1) How can that work? each `edge` in your for-loop is in the list, by construction and (2) you have turned an O(n) algo into O(n^2), which is not a good idea if the list is not small. – assylias May 04 '18 at 10:45

Delete duplicates from an ArrayList using compareTo

4 Answers4