如何使用TreeSet检查重复项

Question

我正在查看TreeSet如何检查重复元素，以下是我的代码：

  import java.util.*;

  public class TreeDemo{

    public static void main(String[] args)
        {
            new TreeDemo().go();
        }

    public void go()
    {
        Song s1 = new Song("song1","artist1");
        Song s2 = new Song("song2","artist2");
        Song s3 = new Song("song3","artist3");
        Song s4 = new Song("song3","artist3");

        Set<Song> tree = new TreeSet<Song>();

        tree.add(s1);
        tree.add(s2);
        tree.add(s3);
        tree.add(s4);

        System.out.println(tree);

    }
}

class Song implements Comparable<Song>{
    private String title;
    private String artist;

    public Song(String t, String a)
    {
        title=t;
        artist=a;
    }

    public String getTitle(){
        return title; 
    }

    public int compareTo(Song s){
        //Song s = (Song)o;
        return title.compareTo(s.getTitle());
    }

public String toString(){
    return title;
}

}

当我执行这段代码时，我得到了以下输出。

[song1, song2, song3]

我的问题是：

• 即使我没有实现hashCode和equals方法（由于需要保持Set排序，我确实实现了Comparable接口），TreeSet如何确定重复项？
• 它是否使用了Object类的默认实现？看起来它在检查时使用了"title"字段，因为当我添加 时它将其视为重复项，但当我添加 时它不将其视为重复项。

谢谢。

- TL36

---

从Comparable接口的文档中可以看到，它说：“强烈建议...自然排序与equals方法保持一致。” - newacct

Answer 1

TreeSet（或者严格来说，支持它的TreeMap）只使用compareTo()函数来比较元素。它不使用Object的.equals()或.hashCode()。此外，如果它使用了其中任何一个，你的输出将会是...

[song1, song2, song3, song3]

因为 Object 的默认实现使用内存地址来测试对象的相等性，而不是它们的成员。

- trutheality

---

是的，我后来意识到 TreeSet 只使用 compareTo (实现 Comparable 接口) 或 compare (实现 Comparator 接口) 进行排序和重复项检查。而 HashSet 使用 equals 和 hashCode。 - Ankur

Answer 2

比较器会返回小于0、等于0或大于0... 因此，equals方法是通过compareTo返回0来实现的。因此

if (node1.compareTo(node2) == 0) 

那么该节点已经在集合中了。

- MeBigFatGuy

Answer 3

TreeSet 实现了一个基于成员排序（通过 Comparable 或 Comparator 接口）而非哈希的平衡二叉搜索树。

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

- ɲeuroburɳ