Java Comparator in Sets with equal items

Question

Normally in a TreeSet there shouldn't be two equal items. But in reality there are often situations where you want to maintain kind of a sorted List instead of a Set. Still there is afaik no TreeList or any SortedList in Java. Though you can of course use Collections.sort().

My question is: what is the proper way to use a TreeSet (or any sorted set) so that it is also capable of containing equal items?

I normally do something like that:

new Comparator<MyObject>() {
    @Override
    public int compare(MyObject o1, MyObject o2) {
        int result = Float.compare(o1.getDistance(), o2.getDistance());
        
        //both distances are equal so we use the object hash as distinctive
        //property.
        if (result == 0) {
            result = Integer.compare(System.identityHashCode(o1), 
                System.identityHashCode(o2))
        }
        return result;
    }
}

While this works very well, this has of course the disadvantage that there is still the slim chance of a hash collision, that would lead to missing objects in the TreeSet.

So I wonder if there is any better way to really distinguish these objects properly?

http://stackoverflow.com/questions/8725387/why-there-is-no-sortedlist-in-java — user2418306, Jul 22 '14 at 17:15
Oh, and don't use a TreeSet that way, unless your purpose to confuse other people. — user2418306, Jul 22 '14 at 17:16
You can add a field to MyObject which should always be unique for different records. Or you can use a List and sort that. — Peter Lawrey, Jul 22 '14 at 17:17
Sometimes the only difference between two object is, that they are two different objects. So of course, if I can add an unique ID i'd use that for sure. But sometimes that's not possible. — Entrusc, Jul 22 '14 at 17:27

laune · Accepted Answer · 2014-07-22T18:00:00.087

2

I have been using

import com.google.common.collect.TreeMultiset;

effortless and successfully.

You shouldn't try to use workarounds when good libraries are around.

There may be other libs as well, of course.

Later

I should have raised a red flag at "equal" in combination with "set". This is a no-no. You can have equal multiple equal keys in a Map.

If you want to store objects repeatedly, even if they are equal, use a List; it's up to you to decide whether an equal element should be added or not.

Another thought:

Maybe you want an IdentityHashMap which uses reference equality rather than equals.

BUT be prepared for endless difficulties if you violate the hashCode/equals contract in your class.

edited Jul 22 '14 at 18:00

answered Jul 22 '14 at 17:17

laune

31,114
3
29
42

I just tested TreeMultiset and it has the same problem. The only difference is that it keeps two identical objects instead of one. But if I want to have two objects that are equal according to the Comparator but still have different properties, then I lose one of these objects. E.g. if I add two objects A(1) with id 1 and A(2) with id 2 and both are equal according to the Comparator then the Multiset only contains two times A(1) but A(2) disappeared. – Entrusc Jul 22 '14 at 17:50
equal is equal is equal. Maybe I should point out... see updated answer, – laune Jul 22 '14 at 17:57
Hmm ... I guess I discovered a very special case where I need multiple values in a sorted collection, that might be equal according to the Comparator but not to hashCode/equals. I think the best way to solve this is to either 1) use the TreeSet and prevent a possible hash collision OR 2) write a red-black tree based List implementation. Still for most of the times your answer will be doing the job, so I accept it as the solution :) – Entrusc Jul 22 '14 at 19:00

score -1 · Answer 2 · answered Jul 21 '16 at 07:27

package newfeature;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;`enter code here`
class employee {
    String name;
    int idno;
    public employee(int idno, String name) {
        this.name = name;
        this.idno = idno;
    }
}
public class setcom {
    public static void main(String[] args) {
        Set<employee> emset = new HashSet<>();
        emset.add(new employee(1, "rohan"));
        emset.add(new employee(2, "sohan"));
        emset.add(new employee(3, "mohan"));
        emset.add(new employee(4, "zohan"));
        for (employee em : emset) {
            System.out.println(em.name);
        }
        Set<employee> sorted = new TreeSet<>(new Comparator<employee>() {
            @Override
            public int compare(employee o1, employee o2) {
                return o1.name.compareTo(o2.name);
            }
        });
        sorted.addAll(emset);
        System.out.println("*******separotor*******");
        for (employee em : sorted) {
            System.out.println(em.name);
        }

    }

}

How is this an answer to the question? It just shows that you can sort items in a tree set, but that was never in question. — Entrusc, Dec 04 '22 at 18:57

Java Comparator in Sets with equal items

2 Answers2