摘要：此項禁止的一個特殊情況是不允許某個包含其自身作為元素。即使的順序與不一致，其行為也是定義良好的它只是違背了接口的常規協定。

Java 中怎樣實現一種即使元素改變依然有序的集合？

起因是在公司做游戲項目的時候遇到一個需求需要實現：

服務器要維護一個幫派成員（Member）的集合，這個集合要按照在線狀態、成員等級和名稱依次有序排列。

由于每時每刻都有玩家在不斷上下線，成員的經驗值也在不斷的改變。因此這個集合的有序狀態在不斷變化，起初的想法是維護一個有序的列表 List 用 Collections.sort() 加上一個定時結構，比如每十分鐘對列表排序一次。然后客戶端請求集合的時候返回這個列表即可。

這種方法的優點是排序是顯而易見的：定時執行、開銷相對小。類似的代碼如下：

class Member {
    // 幫派成員類
}

// 維護有序列表
List orderedMembers = Collections.synchronizedList(new ArrayList());

// 在服務器的刷幀循環中定時排序
@Override
public void onFrameUpdated(long currentTimeMillis) {
    // 十分鐘排序一次
    if (lastSorting + 10 * 60 * 1000 < currentTimeMillis) {
        // 排序 ....
        sort(orderedMembers);
    }
}

我想讓這個集合能實時響應玩家自身的變化，而不是定時掃描一次，于是一開始我是這么嘗試的，繼承 TreeSet 然后實現一個重新排序的回調 ReorderCallback，在任何玩家經驗值改變或是上線下線的時候調用回調的方法 reorder() 來使集合保持有序，代碼如下

interface ReorderCallback {

    // 回調方法，在任何影響排序的狀態值改變的時候被調用
    void reorder(T element);
}

// 自定義了一個 Set 用于監測成員類的變化
class AlwaysOrderedSet extends TreeSet implements ReorderCallback {

    // 實現回調
    @Override
    public void reorder(T element) {
        remove(element);
        add(element);
    }
}

然后在需要的地方回調：

// 幫派成員類
class Member {

    ReorderCallback rCallback;
    
    // 玩家上線
    @Override
    public void onOnline() {
        if (rCallback != null) {
            rCallback.reorder(this);
        }
    }
    
    // 玩家下線
    @Override
    public void onOffline() {
        if (rCallback != null) {
            rCallback.reorder(this);
        }
    }
}

然而，每次玩家狀態改變后調用 reorder() 并不能保持原集合的有序，反而會重復添加 member 對象。因為 TreeSet 無法追蹤元素的變化，就像以下的演示一樣：

public class Sorter {

    public static void main(String[] args) {

        class Student implements Comparable {

            int id;
            String name;
            int age;

            Student(int id, String name, int age) {
                this.id = id;
                this.name = name;
                this.age = age;
            }

            @Override
            public String toString() {
                return String.format("id=%d, name=%s, age=%d", id, name, age);
            }

            @Override
            public int compareTo(Student o) {
                return o.age - this.age;
            }
        }

        Set alwaysOrdered = new TreeSet<>();

        Student a = new Student(1, "Amy", 50);
        Student b = new Student(2, "Bob", 30);
        Student c = new Student(3, "Chris", 40);

        alwaysOrdered.add(a);
        alwaysOrdered.add(b);
        alwaysOrdered.add(c);

        System.out.println("-- before --");
        alwaysOrdered.forEach(System.out::println);

        // 集合元素發生改變
        b.age = 100;

        System.out.println("-- after --");
        alwaysOrdered.forEach(System.out::println);

        // 這里就相當于回調，簡單的 remove 再 add
        alwaysOrdered.remove(b);
        alwaysOrdered.add(b);

        System.out.println("-- after remove and add --");
        alwaysOrdered.forEach(System.out::println);
    }
}

上面的代碼運行結果如下：

-- before --
id=1, name=Amy, age=50
id=3, name=Chris, age=40
id=2, name=Bob, age=30
-- after --
id=1, name=Amy, age=50
id=3, name=Chris, age=40
id=2, name=Bob, age=100
-- after remove and add --
id=2, name=Bob, age=100
id=1, name=Amy, age=50
id=3, name=Chris, age=40
id=2, name=Bob, age=100

可以看出，我試圖改變 Bob 的年齡，然后先后調用集合的 remove 和 add 卻并不是我預想的那樣，remove 實際是返回了 false，因此 b 根本沒有從集合中移除。

百思不得其解后我試圖閱讀 Set 的源代碼，發現了一些線索：

 * 
Note: Great care must be exercised if mutable objects are used as set
 * elements.  The behavior of a set is not specified if the value of an object
 * is changed in a manner that affects equals comparisons while the
 * object is an element in the set.  A special case of this prohibition is
 * that it is not permissible for a set to contain itself as an element.

意思是：

注：如果將可變對象用作 set 元素，那么必須極其小心。如果對象是 set 中某個元素，以一種影響 equals 比較的方式改變對象的值，那么 set 的行為就是不確定的。此項禁止的一個特殊情況是不允許某個 set 包含其自身作為元素。

而 TreeSet 的源碼文檔里是這么寫的

 * 
Note that the ordering maintained by a set (whether or not an explicit
 * comparator is provided) must be consistent with equals if it is to
 * correctly implement the {@code Set} interface.  (See {@code Comparable}
 * or {@code Comparator} for a precise definition of consistent with
 * equals.)  This is so because the {@code Set} interface is defined in
 * terms of the {@code equals} operation, but a {@code TreeSet} instance
 * performs all element comparisons using its {@code compareTo} (or
 * {@code compare}) method, so two elements that are deemed equal by this method
 * are, from the standpoint of the set, equal.  The behavior of a set
 * is well-defined even if its ordering is inconsistent with equals; it
 * just fails to obey the general contract of the {@code Set} interface.

大致意思是：

注意，如果要正確實現 Set 接口，則 set 維護的順序（無論是否提供了顯式比較器）必須與 equals 一致。（關于與 equals 一致 的精確定義，請參閱 Comparable 或 Comparator。）這是因為 Set 接口是按照 equals 操作定義的，但 TreeSet 實例使用它的 compareTo（或 compare）方法對所有元素進行比較，因此從 set 的觀點來看，此方法認為相等的兩個元素就是相等的。即使 set 的順序與 equals 不一致，其行為也是定義良好的；它只是違背了 Set 接口的常規協定。

總的來說就是，Set 的定義是不包含重復元素的集合，這個不重復的特性由它維護的元素的 equals() 方法來保證，這個好理解，關鍵是下面。TreeSet 并不完全遵守這個定義，它的不重復性由元素的 compareTo() 方法來保證。

因此，即便元素重寫了 equals() 方法和 hashCode() 方法，當元素 E 的值發生改變時，對于 TreeSet，對 contains(E) 的調用始終返回 false，因此對 remove(E) 的調用也始終返回 false，因為 TreeSet 只依據 compareTo 方法來判斷兩個元素是否相等并進行排序。

所以對于之前的 Student 示例，解決方法就是讓 Student 實現 Comparable 并重寫 compareTo 方法，用該方法代替 equals() 方法去定義對象是否相等的邏輯，同時加上排序：

class Student implements Comparable {

    int id;
    String name;
    int age;

    Student(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return String.format("id=%d, name=%s, age=%d", id, name, age);
    }

    // compareTo 方法有兩個作用：1、代替 equals，2、compareTo
    @Override
    public int compareTo(Student o) {
        // 這里的判斷非常關鍵，代替了 equals() 方法
        if (id == o.id) {
        return 0;
    }
                
    // 這里再進行原始的 compareTo 判斷
    if (age == o.age) {
        if (name.equals(o.name)) {
            return id - o.id;
        }
        return name.compareTo(o.name);
    }
    return o.age - age;
    }
}

改寫后的 Student 的代碼運行結果如下：

id=1, name=Amy, age=50
id=3, name=Chris, age=40
id=2, name=Bob, age=30
-- after --
id=1, name=Amy, age=50
id=3, name=Chris, age=100
id=2, name=Bob, age=30
-- after remove and add --
id=3, name=Chris, age=100
id=1, name=Amy, age=50
id=2, name=Bob, age=30