Java - TreeSet accepting duplicates

Question

I'm having some problems with TreeSet: why does this one accept duplicates? I thought TreeSets detected them through the Comparator, and automatically remove them. Please help me, I'm kind of new to both Java and StackOverflow.

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class SortedSongs
{   
    private Set songs;
    public SortedSongs()
    {
         Comparator<Song> comp = (Song c1, Song c2)-> c1.toString().compareTo(c2.toString());
         songs = new TreeSet<>(comp);
    }
}

edit: this is how I implemented hashCode and equals:

@Override
public int hashCode()
{
    return Objects.hash(name, author);
}

@Override
public boolean equals(Object o)
{
    return o == null ? false : o.getClass() != getClass() ? false
        : o.hashCode() == hashCode();
}

edit2: This is the updated equals method, toString and compareTo for class Song

@Override
public boolean equals(Object o)
{
    if (this==o) return true;
    if (getClass()!=o.getClass()) return false;
    return name.equals(((Song) o).name) && author.equals(((Song) o).author);
}
@Override
public String toString() {return name + " - " + author;}

public int compareTo(Song other)
{
    if (name.equals(other.name))
        return author.equals(other.author) ? 0 : author.compareTo(other.author);
    return name.compareTo(other.name);
}

So now the Comparator in SortedSongs

Comparator<Song> comp = (Song c1, Song c2)-> c1.compareTo(c2);

Still not working though, I feel as if I'm missing something obvious

edit3: Solved, I actually made a mistake with my Test class. Embarrassing. Sorry, didn't mean to waste your time, I hope this will be helpful to someone.

The issue may be a bit subtle: You are comparing the songs by their string representation. You should show us how `toString` is implemented, and preferably also show which `Song` objects end up as duplicates. In general, the comparator has to be *consistent with equals* to obey the contract of the `Set` interface, but even without a proper `equals` implementation, you should not see duplicates. — Marco13, May 02 '18 at 23:28
(And a side note: Your current `equals` implementation is **not** valid. The general rule is: **If** objects are equal according to the `equals` method, **then** they must have the same `hashCode`. But if they have the same `hashCode`, then they are *not necessarily* equal according to the `equals` method. Only a side note, because it *should* not be relevant for the issue that you are observing) — Marco13, May 02 '18 at 23:34
Your `equals` and `Comparator` are not quite correct. Try to fix them first so that they compare `Song`s field by field. — lexicore, May 02 '18 at 23:34
The equals method is absolutely wrong. Joshua Bloch tells you how to override equals and hashCode correct in chapter 3 of "Effective Java". — duffymo, May 02 '18 at 23:56
What are the fields, `name` and `author`? Also, can you give an example of some input that is causing it to fail? — matt, May 03 '18 at 07:51

score 5 · Answer 1 · answered May 02 '18 at 23:42

5

TreeSet is implemented with a balanced binary tree in Java (actually RedBlack tree) . So it does not use the equals method. It uses the Comparator.

Now the problem about your implementation is about your comparator. Your comparator is based on the toString method. By default java returns the name of the object's class plus its hash code. So by default the output of toString will be the same for two objects if and only if they are pointing to the same memory reference. You need to make sure that you have override the toString method in your class as you comparator is based on that.

To resolve the issue, you need to define a comparator that reflect the comparison logic of your program.

answered May 02 '18 at 23:42

MigSena

218
2
7

1

The issue is clearly related to `toString`, but as long as we don't know whether (or how) `toString` was overridden, it's hard to give a definite answer here. According to the name (`SortedSongs`), I'm pretty sure that there is a `toString` implementation, and the intention was to sort the songs alphabetically - but that's also just a guess until now.. – Marco13 May 02 '18 at 23:46
1

**Don't use `toString()` at all** (for _anything_, _ever_). Make the `Comparator` do its own work without any help from `toString()`, looking directly at whatever data comprises a `Song`-- title, writer, singer, arranger, whatever -- then in won't matter whether `toString()` is right or wrong, overridden or not.. – Kevin Anderson May 03 '18 at 00:16

score 0 · Answer 2 · answered May 28 '19 at 18:53

TreeSet delegates under the hood to TreeMap implementation with dummy values. So, instead of allowing duplicates with tricky comparator, it would be easier and more memory-efficient to switch to TreeMap with values holding duplicate counts.

Here is an example: How do I use a TreeSet in Java that allows Duplicates?.

Java - TreeSet accepting duplicates

2 Answers2