Java 中實現集合的 keep in order （后續）

loostudy 發布于2019-08-14 15:30 / 1744人閱讀

摘要：寫完上一篇中實現集合的后，自己又進行了一番探索，結合在公司項目的實際測試后，總結了一個更加有效地基于紅黑樹的結構來實現集合的，由于使用二叉樹來保存有序集合，因此對集合的增加刪除查找的時間復雜度均為。

寫完上一篇「Java 中實現集合的 keep in order」后，自己又進行了一番探索，結合在公司項目的實際測試后，總結了一個更加有效地、基于 TreeSet（紅黑樹）的結構來實現集合的 keep in order，由于使用二叉樹來保存有序集合，因此對集合的增加、刪除、查找的時間復雜度均為 log(n)。

集合（Set）的約定

Java 中對集合（Set）一般做法是：為了代碼的健壯性，盡量在 Set 中保存不可變的對象。因為不管是 HashSet 還是 TreeSet，他們都依賴元素自身的特性來保證集合的不重復性。如 HashSet 依賴元素的 equals 和 hashCode 方法，TreeSet 依賴元素的 compareTo 方法或自定義的 Comparator。

元素改變情況下保持集合有序

首先，公司項目里，服務器維護了一個玩家的集合：

class PlayerManager {
    
    // 玩家的 Map，<玩家 id -> 玩家實體>
    Map map = new ConcurrentHashMap<>();
}

// 玩家實體
interface Player {
    
    int getId();
    
    int getMoney();
    
    void setMoney(int money);
}

這個 map 將成為數據源，它不一定是有序。現在增加一個成員：

// 可重排序的集合，保存不可變對象：玩家 id
Set reorderableSet;

這個集合記錄這所有玩家的 id 值，并以某種順序進行排序，排序的規則視需求而定，假如要以玩家擁有的金錢數來做財富排行榜。
由于玩家的財富值始終在發生變化，因此我定義一個接口來感知這種變化：

interface Reorderable {

    // 這個方法用于重新計算元素 E 在集合中的索引
    void recomputeOrder(E element, ElementChangedCallback callback);

    // 這是一個回調，處理元素值改變的代碼
    interface ElementChangedCallback {

        void onElementChanged(E element);
    }
}

然后用 TreeSet 的子類實現上面的 Reorderable 接口來構造一個可重排序的集合：

class ReorderableSet extends TreeSet implements Reorderable {

    // 使用自定義的比較器
    public ReorderableSet(Comparator comparator) {
        super(comparator);
    }

    @Override
    public void recomputeOrder(E element, ElementChangedCallback callback) {
        if (contains(element)) {
            // 先將元素從集合中移除，時間復雜度 log(n)
            remove(element);
            // 再使用回調去改變元素的值
            callback.onElementChanged(element);
            // 在將元素添加到集合里，時間復雜度 log(n)
            add(element);
        }
    }
}

因為是實現一個財富排行榜，所以定義排序規則為簡單的比較一下金錢數目即可：

// 這里的 Integer 代表玩家 id
class MoneyComparator implements Comparator {

    @Override
    public int compare(Integer A, Integer B) {
        
        // 從服務器維護的玩家集合中獲取玩家的引用
        Player playerA = map.get(A);
        Player playerB = map.get(B);
        
        // 降序排列
        return playerB.getMoney() - playerA.getMoney();
    }
}

這時候可以構造之前定義的 Set reorderableSet 了：

Set reorderableSet = new ReorderableSet<>(new MoneyComparator());

要響應玩家金錢的變化，則構造一個實現 ElementChangedCallback 接口的類，并把它放在任何玩家金錢改變的地方：

class UpdateMoney implements Reorderable.ElementChangedCallback {

    int money;

    UpdateMoney(int money) {
        this.money= money;
    }

    @Override
    public void onElementChanged(Integer playerId) {
        // 玩家金錢改變
        Player player = map.get(playerId);
        player.setMoney(money);
    }
}

玩家金錢改變的時候調用一下代碼，比如買東西的時候

void buyGood(Player player, int cost) {
    Reorderable reorderableSet = ......; // 獲得引用
    int moneyRemain = player.getMoney() - cost;
    
    // 構造 UpdateMoney 回調
    reorderableSet .recomputeOrder(player.getId(), new UpdateMoney(moneyRemain);
}

因此，就可以實現集合（Set）在元素值改變時保持有序了，由于 TreeSet 基于紅黑樹實現，對它的查找添加刪除均很快。

總結

通用的框架就像下面這樣：

class ReorderableSet extends TreeSet implements Reorderable {

    public ReorderableSet() {
    }

    public ReorderableSet(Comparator comparator) {
        super(comparator);
    }

    public ReorderableSet(Collection c) {
        super(c);
    }

    public ReorderableSet(SortedSet s) {
        super(s);
    }

    @Override
    public void recomputeOrder(E element, ElementChangedCallback callback) {
        if (contains(element)) {
            // 先將元素從集合中移除，時間復雜度 log(n)
            remove(element);
            // 再使用回調去改變元素的值
            callback.onElementChanged(element);
            // 在將元素添加到集合里，時間復雜度 log(n)
            add(element);
        }
    }
}

interface Reorderable {

    void recomputeOrder(E element, ElementChangedCallback callback);

    interface ElementChangedCallback {

        void onElementChanged(E element);
    }
}

考慮到線程安全，可以在 recomputeOrder 中進行加鎖操作。

GPU云服務器云服務器 java中實現線程 java類中實現換行 java中實現是什么 java中實現多線程

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65812.html

Java 中實現集合的 keep in order

摘要：此項禁止的一個特殊情況是不允許某個包含其自身作為元素。即使的順序與不一致，其行為也是定義良好的它只是違背了接口的常規協定。原問題 Java 中怎樣實現一種即使元素改變依然有序的集合？問題由來起因是在公司做游戲項目的時候遇到一個需求需要實現：服務器要維護一個幫派成員（Member）的集合，這個集合要按照在線狀態、成員等級和名稱依次有序排列。由于每時每刻都有玩家在不斷上下線，成員...

gyl_coder 2019-08-14 15:27 評論0 收藏0
Spring核心接口之Ordered

摘要：一接口介紹中提供了一個接口。從單詞意思就知道接口的作用就是用來排序的。類實現了接口的一個比較器。三中使用接口在的例子在配置文件中添加，那么默認會注入和這兩個類。一、Ordered接口介紹Spring中提供了一個Ordered接口。從單詞意思就知道Ordered接口的作用就是用來排序的。Spring框架是一個大量使用策略設計模式的框架，這意味著有很多相同接口的實現類，那么必定會有優先級...

cartoon 2019-08-16 10:58 評論0 收藏0
LinkedHashMap 源碼詳細分析（JDK1.8）

摘要：關于的源碼分析，本文并不打算展開講了。大家可以參考我之前的一篇文章源碼詳細分析。在刪除節點時，父類的刪除邏輯并不會修復所維護的雙向鏈表，這不是它的職責。在節分析鏈表建立過程時，我故意忽略了部分源碼分析。 1. 概述 LinkedHashMap 繼承自 HashMap，在 HashMap 基礎上，通過維護一條雙向鏈表，解決了 HashMap 不能隨時保持遍歷順序和插入順序一致的問題。除此...

Harriet666 2019-08-15 13:49 評論0 收藏0
基于LinkedBlockingQueue實現股票交易系統

摘要：與基于數組的隊列相同，重載的構造函數可以接受集合指定的初始值。這種隊列比基于數組阻塞隊列具有更高的吞吐量。創建個交易者實例，將自己出售的訂單放入隊列中，每個出售訂單都將會有隨機的交易量。要使用基于優先級的隊列，需要提供適當的比較器。阻塞隊列在阻塞隊列的幫助下，許多同步問題都可以被公式化。阻塞隊列是隊列，當線程試圖對空隊列進行出列操作，或試圖向滿的隊列中插入條目時，隊列就會阻塞。直到...

30e8336b8229 2019-08-15 14:16 評論0 收藏0
Java? 教程（高級并發對象）

高級并發對象到目前為止，本課程重點關注從一開始就是Java平臺一部分的低級別API，這些API適用于非常基礎的任務，但更高級的任務需要更高級別的構建塊，對于充分利用當今多處理器和多核系統的大規模并發應用程序尤其如此。在本節中，我們將介紹Java平臺5.0版中引入的一些高級并發功能，大多數這些功能都在新的java.util.concurrent包中實現，Java集合框架中還有新的并發數據結構。 ...

xiaotianyi 2019-08-16 14:33 評論0 收藏0