Java 中实现集合的 keep in order （后续）

loostudy 发布于2019-08-14 15:30 / 1742人阅读

摘要：写完上一篇中实现集合的后，自己又进行了一番探索，结合在公司项目的实际测试后，总结了一个更加有效地基于红黑树的结构来实现集合的，由于使用二叉树来保存有序集合，因此对集合的增加删除查找的时间复杂度均为。

写完上一篇「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中实现多线程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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