Java 中實(shí)現(xiàn)集合的 keep in order （后續(xù)）

loostudy 發(fā)布于2019-08-14 15:30 / 1815人閱讀

摘要：寫(xiě)完上一篇中實(shí)現(xiàn)集合的后，自己又進(jìn)行了一番探索，結(jié)合在公司項(xiàng)目的實(shí)際測(cè)試后，總結(jié)了一個(gè)更加有效地基于紅黑樹(shù)的結(jié)構(gòu)來(lái)實(shí)現(xiàn)集合的，由于使用二叉樹(shù)來(lái)保存有序集合，因此對(duì)集合的增加刪除查找的時(shí)間復(fù)雜度均為。

寫(xiě)完上一篇「Java 中實(shí)現(xiàn)集合的 keep in order」后，自己又進(jìn)行了一番探索，結(jié)合在公司項(xiàng)目的實(shí)際測(cè)試后，總結(jié)了一個(gè)更加有效地、基于 TreeSet（紅黑樹(shù)）的結(jié)構(gòu)來(lái)實(shí)現(xiàn)集合的 keep in order，由于使用二叉樹(shù)來(lái)保存有序集合，因此對(duì)集合的增加、刪除、查找的時(shí)間復(fù)雜度均為 log(n)。

集合（Set）的約定

Java 中對(duì)集合（Set）一般做法是：為了代碼的健壯性，盡量在 Set 中保存不可變的對(duì)象。因?yàn)椴还苁?HashSet 還是 TreeSet，他們都依賴元素自身的特性來(lái)保證集合的不重復(fù)性。如 HashSet 依賴元素的 equals 和 hashCode 方法，TreeSet 依賴元素的 compareTo 方法或自定義的 Comparator。

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

首先，公司項(xiàng)目里，服務(wù)器維護(hù)了一個(gè)玩家的集合：

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

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

這個(gè) map 將成為數(shù)據(jù)源，它不一定是有序。現(xiàn)在增加一個(gè)成員：

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

這個(gè)集合記錄這所有玩家的 id 值，并以某種順序進(jìn)行排序，排序的規(guī)則視需求而定，假如要以玩家擁有的金錢數(shù)來(lái)做財(cái)富排行榜。
由于玩家的財(cái)富值始終在發(fā)生變化，因此我定義一個(gè)接口來(lái)感知這種變化：

interface Reorderable {

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

    // 這是一個(gè)回調(diào)，處理元素值改變的代碼
    interface ElementChangedCallback {

        void onElementChanged(E element);
    }
}

然后用 TreeSet 的子類實(shí)現(xiàn)上面的 Reorderable 接口來(lái)構(gòu)造一個(gè)可重排序的集合：

class ReorderableSet extends TreeSet implements Reorderable {

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

    @Override
    public void recomputeOrder(E element, ElementChangedCallback callback) {
        if (contains(element)) {
            // 先將元素從集合中移除，時(shí)間復(fù)雜度 log(n)
            remove(element);
            // 再使用回調(diào)去改變?cè)氐闹?            callback.onElementChanged(element);
            // 在將元素添加到集合里，時(shí)間復(fù)雜度 log(n)
            add(element);
        }
    }
}

因?yàn)槭菍?shí)現(xiàn)一個(gè)財(cái)富排行榜，所以定義排序規(guī)則為簡(jiǎn)單的比較一下金錢數(shù)目即可：

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

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

這時(shí)候可以構(gòu)造之前定義的 Set reorderableSet 了：

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

要響應(yīng)玩家金錢的變化，則構(gòu)造一個(gè)實(shí)現(xiàn) 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);
    }
}

玩家金錢改變的時(shí)候調(diào)用一下代碼，比如買東西的時(shí)候

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

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

總結(jié)

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

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)) {
            // 先將元素從集合中移除，時(shí)間復(fù)雜度 log(n)
            remove(element);
            // 再使用回調(diào)去改變?cè)氐闹?            callback.onElementChanged(element);
            // 在將元素添加到集合里，時(shí)間復(fù)雜度 log(n)
            add(element);
        }
    }
}

interface Reorderable {

    void recomputeOrder(E element, ElementChangedCallback callback);

    interface ElementChangedCallback {

        void onElementChanged(E element);
    }
}

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

GPU云服務(wù)器云服務(wù)器 java中實(shí)現(xiàn)線程 java類中實(shí)現(xiàn)換行 java中實(shí)現(xiàn)是什么 java中實(shí)現(xiàn)多線程

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65812.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

loostudy

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

免費(fèi)英文字體Hanson Bold 無(wú)襯線粗體字體無(wú)需商業(yè)授權(quán)

閱讀 4278·2021-09-24 10:24
虛擬主機(jī)怎么傳文件-虛擬主機(jī)怎么上傳文件？

閱讀 1521·2021-09-22 16:01
程序員的算法趣題Q12: 平方根數(shù)字

閱讀 2812·2021-09-06 15:02
關(guān)于CSS的position屬性

閱讀 1089·2019-08-30 13:01
探究行內(nèi)元素和塊級(jí)元素

閱讀 1067·2019-08-30 10:52
：：before和：：after的詳細(xì)介紹

閱讀 693·2019-08-29 16:36
左右兩側(cè)寬度固定,中間自適應(yīng)之【圣杯+雙飛翼】實(shí)現(xiàn)

閱讀 2298·2019-08-29 12:51
Week 1：那些值得一閱的好文章

閱讀 2414·2019-08-28 18:29

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

Java 中實(shí)現(xiàn)集合的 keep in order （后續(xù)）

相關(guān)文章