转载

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

写完上一篇「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 中进行加锁操作。

原文 https://segmentfault.com/a/1190000004963590

正文到此结束