资讯专栏INFORMATION COLUMN

Java 中实现集合的 keep in order

gyl_coder / 2480人阅读

摘要:此项禁止的一个特殊情况是不允许某个包含其自身作为元素。即使的顺序与不一致,其行为也是定义良好的它只是违背了接口的常规协定。

原问题

Java 中怎样实现一种即使元素改变依然有序的集合?

问题由来

起因是在公司做游戏项目的时候遇到一个需求需要实现:

服务器要维护一个帮派成员(Member)的集合,这个集合要按照在线状态成员等级名称依次有序排列

由于每时每刻都有玩家在不断上下线,成员的经验值也在不断的改变。因此这个集合的有序状态在不断变化,起初的想法是维护一个有序的列表 ListCollections.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 的年龄,然后先后调用集合的 removeadd 却并不是我预想的那样,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 一致 的精确定义,请参阅 ComparableComparator。)这是因为 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

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

转载请注明本文地址:https://www.ucloud.cn/yun/65775.html

相关文章

  • Java 中实集合 keep in order (后续)

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

    loostudy 评论0 收藏0
  • Spring核心接口之Ordered

    摘要:一接口介绍中提供了一个接口。从单词意思就知道接口的作用就是用来排序的。类实现了接口的一个比较器。三中使用接口在的例子在配置文件中添加,那么默认会注入和这两个类。 一、Ordered接口介绍Spring中提供了一个Ordered接口。从单词意思就知道Ordered接口的作用就是用来排序的。Spring框架是一个大量使用策略设计模式的框架,这意味着有很多相同接口的实现类,那么必定会有优先级...

    cartoon 评论0 收藏0
  • 基于LinkedBlockingQueue实股票交易系统

    摘要:与基于数组的队列相同,重载的构造函数可以接受集合指定的初始值。这种队列比基于数组阻塞队列具有更高的吞吐量。创建个交易者实例,将自己出售的订单放入队列中,每个出售订单都将会有随机的交易量。要使用基于优先级的队列,需要提供适当的比较器。 阻塞队列 在阻塞队列的帮助下,许多同步问题都可以被公式化。阻塞队列是队列,当线程试图对空队列进行出列操作,或试图向满的队列中插入条目时,队列就会阻塞。直到...

    30e8336b8229 评论0 收藏0
  • 从零开始实一个简易Java MVC框架(六)--加强AOP功能

    摘要:在前面的文章中实现的功能时,目标类都只能被一个切面代理,如果想要生成第二个代理类,就会把之前的代理类覆盖。改装原有功能现在要改装原来的的实现代码,让的功能加入到框架中为了让切面能够排序,先添加一个注解,用于标记排序。 前言 在前面从零开始实现一个简易的Java MVC框架(四)--实现AOP和从零开始实现一个简易的Java MVC框架(五)--引入aspectj实现AOP切点这两节文章...

    Loong_T 评论0 收藏0
  • python设计模式-抽象工厂模式

    摘要:源码参考抽象工厂模式抽象工厂模式提供一个接口,用于创建相关或依赖对象的家族,而不需要指定具体类。工厂方法模式和抽象工厂模式如何选择开始的时候,可以选择工厂方法模式,因为他很简单只需要继承,并实现工厂方法即可。 问题:在上一篇 python设计模式:工厂方法模式我们尝试使用工厂方法创建了披萨店,现在为了保证披萨加盟店也能有良好的声誉,我们需要统一原材料,这个该如何做呢? 为了确保每家加盟...

    seal_de 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<