摘要:此项禁止的一个特殊情况是不允许某个包含其自身作为元素。即使的顺序与不一致,其行为也是定义良好的它只是违背了接口的常规协定。
原问题
Java 中怎样实现一种即使元素改变依然有序的集合?
问题由来起因是在公司做游戏项目的时候遇到一个需求需要实现:
服务器要维护一个帮派成员(Member)的集合,这个集合要按照在线状态、成员等级和名称依次有序排列。
由于每时每刻都有玩家在不断上下线,成员的经验值也在不断的改变。因此这个集合的有序状态在不断变化,起初的想法是维护一个有序的列表 List
这种方法的优点是排序是显而易见的:定时执行、开销相对小。类似的代码如下:
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
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65775.html
摘要:写完上一篇中实现集合的后,自己又进行了一番探索,结合在公司项目的实际测试后,总结了一个更加有效地基于红黑树的结构来实现集合的,由于使用二叉树来保存有序集合,因此对集合的增加删除查找的时间复杂度均为。 写完上一篇「Java 中实现集合的 keep in order」后,自己又进行了一番探索,结合在公司项目的实际测试后,总结了一个更加有效地、基于 TreeSet(红黑树)的结构来实现集合的...
摘要:一接口介绍中提供了一个接口。从单词意思就知道接口的作用就是用来排序的。类实现了接口的一个比较器。三中使用接口在的例子在配置文件中添加,那么默认会注入和这两个类。 一、Ordered接口介绍Spring中提供了一个Ordered接口。从单词意思就知道Ordered接口的作用就是用来排序的。Spring框架是一个大量使用策略设计模式的框架,这意味着有很多相同接口的实现类,那么必定会有优先级...
摘要:与基于数组的队列相同,重载的构造函数可以接受集合指定的初始值。这种队列比基于数组阻塞队列具有更高的吞吐量。创建个交易者实例,将自己出售的订单放入队列中,每个出售订单都将会有随机的交易量。要使用基于优先级的队列,需要提供适当的比较器。 阻塞队列 在阻塞队列的帮助下,许多同步问题都可以被公式化。阻塞队列是队列,当线程试图对空队列进行出列操作,或试图向满的队列中插入条目时,队列就会阻塞。直到...
摘要:在前面的文章中实现的功能时,目标类都只能被一个切面代理,如果想要生成第二个代理类,就会把之前的代理类覆盖。改装原有功能现在要改装原来的的实现代码,让的功能加入到框架中为了让切面能够排序,先添加一个注解,用于标记排序。 前言 在前面从零开始实现一个简易的Java MVC框架(四)--实现AOP和从零开始实现一个简易的Java MVC框架(五)--引入aspectj实现AOP切点这两节文章...
摘要:源码参考抽象工厂模式抽象工厂模式提供一个接口,用于创建相关或依赖对象的家族,而不需要指定具体类。工厂方法模式和抽象工厂模式如何选择开始的时候,可以选择工厂方法模式,因为他很简单只需要继承,并实现工厂方法即可。 问题:在上一篇 python设计模式:工厂方法模式我们尝试使用工厂方法创建了披萨店,现在为了保证披萨加盟店也能有良好的声誉,我们需要统一原材料,这个该如何做呢? 为了确保每家加盟...
阅读 3756·2023-04-25 16:32
阅读 2107·2021-09-28 09:36
阅读 2020·2021-09-06 15:02
阅读 645·2021-09-02 15:21
阅读 902·2019-08-30 15:56
阅读 3492·2019-08-30 15:45
阅读 1696·2019-08-30 13:09
阅读 356·2019-08-29 16:05