写完上一篇「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<Integer, Player> map = new ConcurrentHashMap<>();
}
// 玩家实体
interface Player {
int getId();
int getMoney();
void setMoney(int money);
}
这个 map
将成为数据源,它不一定是有序。现在增加一个成员:
// 可重排序的集合,保存不可变对象:玩家 id
Set<Integer> reorderableSet;
这个集合记录这所有玩家的 id 值,并以某种顺序进行排序,排序的规则视需求而定,假如要以玩家拥有的金钱数来做财富排行榜。
由于玩家的财富值始终在发生变化,因此我定义一个接口来感知这种变化:
interface Reorderable<E> {
// 这个方法用于重新计算元素 E 在集合中的索引
void recomputeOrder(E element, ElementChangedCallback<E> callback);
// 这是一个回调,处理元素值改变的代码
interface ElementChangedCallback<E> {
void onElementChanged(E element);
}
}
然后用 TreeSet
的子类实现上面的 Reorderable
接口来构造一个可重排序的集合:
class ReorderableSet<E> extends TreeSet<E> implements Reorderable<E> {
// 使用自定义的比较器
public ReorderableSet(Comparator<? super E> comparator) {
super(comparator);
}
@Override
public void recomputeOrder(E element, ElementChangedCallback<E> callback) {
if (contains(element)) {
// 先将元素从集合中移除,时间复杂度 log(n)
remove(element);
// 再使用回调去改变元素的值
callback.onElementChanged(element);
// 在将元素添加到集合里,时间复杂度 log(n)
add(element);
}
}
}
因为是实现一个财富排行榜,所以定义排序规则为简单的比较一下金钱数目即可:
// 这里的 Integer 代表玩家 id
class MoneyComparator implements Comparator<Integer> {
@Override
public int compare(Integer A, Integer B) {
// 从服务器维护的玩家集合中获取玩家的引用
Player playerA = map.get(A);
Player playerB = map.get(B);
// 降序排列
return playerB.getMoney() - playerA.getMoney();
}
}
这时候可以构造之前定义的 Set<Player> reorderableSet
了:
Set<Player> reorderableSet = new ReorderableSet<>(new MoneyComparator());
要响应玩家金钱的变化,则构造一个实现 ElementChangedCallback
接口的类,并把它放在任何玩家金钱改变的地方:
class UpdateMoney implements Reorderable.ElementChangedCallback<Integer> {
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<Integer> reorderableSet = ......; // 获得引用
int moneyRemain = player.getMoney() - cost;
// 构造 UpdateMoney 回调
reorderableSet .recomputeOrder(player.getId(), new UpdateMoney(moneyRemain);
}
因此,就可以实现集合(Set)在元素值改变时保持有序了,由于 TreeSet
基于红黑树实现,对它的查找添加删除均很快。
总结
通用的框架就像下面这样:
class ReorderableSet<E> extends TreeSet<E> implements Reorderable<E> {
public ReorderableSet() {
}
public ReorderableSet(Comparator<? super E> comparator) {
super(comparator);
}
public ReorderableSet(Collection<? extends E> c) {
super(c);
}
public ReorderableSet(SortedSet<E> s) {
super(s);
}
@Override
public void recomputeOrder(E element, ElementChangedCallback<E> callback) {
if (contains(element)) {
// 先将元素从集合中移除,时间复杂度 log(n)
remove(element);
// 再使用回调去改变元素的值
callback.onElementChanged(element);
// 在将元素添加到集合里,时间复杂度 log(n)
add(element);
}
}
}
interface Reorderable<E> {
void recomputeOrder(E element, ElementChangedCallback<E> callback);
interface ElementChangedCallback<E> {
void onElementChanged(E element);
}
}
考虑到线程安全,可以在 recomputeOrder
中进行加锁操作。