自定義 Java 型別的 TreeMapTreeSet

由於 TreeMaps 和 TreeSets 根據其自然順序維護鍵/元素。因此,TreeMap 鍵和 TreeSet 元素必須相互比較。

假設我們有一個自定義 Person 類:

public class Person  {

    private int id;
    private String firstName, lastName;
    private Date birthday;

    //... Constuctors, getters, setters and various methods
}

如果我們將它原樣儲存在 TreeSet(或 TreeMap 中的 Key)中:

TreeSet<Person2> set = ...      
set.add(new Person(1,"first","last",Date.from(Instant.now())));

然後我們會遇到像這樣的異常:

Exception in thread "main" java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)

為了解決這個問題,我們假設我們想要根據其 id(private int id)的順序來命令 Person 例項。我們可以通過以下兩種方式之一來實現:

  1. 一種解決方案是修改 Person,以便實現 Comparable 介面

    public class Person implements Comparable<Person> {
        private int id;
        private String firstName, lastName;
        private Date birthday;
    
        //... Constuctors, getters, setters and various methods
    
        @Override
        public int compareTo(Person o) {
            return Integer.compare(this.id, o.id); //Compare by id
        }
    }
    
  2. 另一個解決方案是為 TreeSet 提供一個比較器

Version >= Java SE 8

TreeSet<Person> treeSet = new TreeSet<>((personA, personB) -> Integer.compare(personA.getId(), personB.getId()));
TreeSet<Person> treeSet = new TreeSet<>(new Comparator<Person>(){
    @Override
    public int compare(Person personA, Person personB) {
        return Integer.compare(personA.getId(), personB.getId());
    }
});

但是,這兩種方法都有兩點需要注意:

  1. 將例項插入 TreeSet / TreeMap 後,不要修改用於排序的任何欄位,這一點非常重要。在上面的示例中,如果我們更改已插入集合的人員的 id,我們可能會遇到意外行為。

  2. 正確和一致地實施比較非常重要。根據 Javadoc

實現者必須確保所有 x 和 y 的 sgn(x.compareTo(y)) == -sgn(y.compareTo(x))。 (這意味著如果 y.compareTo(x) 丟擲異常,x.compareTo(y) 必須丟擲異常。)

實現者還必須確保關係是可傳遞的:(x.compareTo(y)>0 && y.compareTo(z)>0) 暗示了 x.compareTo(z)>0

最後,實現者必須確保 x.compareTo(y)==0 暗示 sgn(x.compareTo(z)) == sgn(y.compareTo(z)),對於所有 z。