如何实现维护插入顺序的并发Set

Question

我需要一个 Set 实现，它可以让我维护插入顺序并且仍然可以同时修改（如不抛出 ConcurrentModificationException）。

我尝试将 ConcurrentSkipListSet 与我自己的比较器一起使用 - 示例代码：

public static void main(String[] str){
        ConcurrentSkipListSet set  = new ConcurrentSkipListSet(new Comparator() {

            public int compare(Object o1, Object o2) {
                if(o1.equals(o2)){
                    return 0;
                }
                return -1;
            }
        });
        set.add("d");
        set.add("b");
        set.add("a");
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        set.add("c");
        set.add("b");

        System.out.println(set);
        set.remove("b");
        System.out.println(set);
    }

但看来该比较器是 #fail，因为该集打印：
[b, c, a, b ，d] 。如果 b 出现两次则不成立。
我还应该考虑其他选择吗？

Answer 1

您定义的比较器不遵守总订单属性。对于两个对象，其中一个应该小于另一个，或者另一个小于第一个。

在您的情况下，如果对象不相等，则每个对象都小于另一个对象。

由于您实例化 ConcurrentSkipListSet 时没有任何类型参数来说明集合中元素的类型，因此除非使用强制转换，否则定义比较器时会遇到麻烦。但如果您创建一个新的 ConcurrentSkipListSet，定义比较器会更容易，因为您会知道您的对象是字符串。

Answer 2

您可以定义一个比较器，它将保持字符串的插入顺序并使用它，它不会很漂亮，但由于总是为每个新元素调用比较器，您需要做的就是这样：

public void testInsertionOrderSkipListSet() {
  Comparator<String> insertionOrderComparator = new Comparator<String>() {

    private final ConcurrentHashMap<String, Integer> order = new ConcurrentHashMap<String, Integer>();
    @Override
    public int compare(String o1, String o2) {
      if (!order.contains(o2)) //only happens on second insert
        order.put(o2, 0);
      if (order.containsKey(o1))
        return order.get(o1).compareTo(order.get(o2));
      order.put(o1, order.size());
      return 1;
    }
  };
  ConcurrentSkipListSet<String> set = new ConcurrentSkipListSet<String>(insertionOrderComparator);

  set.add("a");
  set.add("c");
  set.add("e");
  set.add("b");
  set.add("d");
  set.add("c");
  assertArrayEquals(new String[] { "a", "c", "e", "b", "d"}, set.toArray(new String[]{}));
}

嘿，我说过了不漂亮...

Answer 3

我几乎使用了@Asaf的解决方案，但是我对其进行了一些改进，以使其也适用于删除操作：

class ConcurrentInsertionOrderSet extends ConcurrentSkipListSet{
        Map<Object, Integer> orderMap;
        final AtomicInteger increment = new AtomicInteger();
        public ConcurrentInsertionOrderSet(final Map<Object, Integer> orderMap) {
            super(new Comparator<Object>() {      
                public int compare(Object o1, Object o2) {
                    return (orderMap.get(o1).compareTo(orderMap.get(o2)));
                }
            });
            this.orderMap = orderMap;
        }

        @Override
        public boolean add(Object o) {
            if (!orderMap.containsKey(o)) 
                orderMap.put(o, increment.incrementAndGet());
            return super.add(o);
        }
        @Override
        public boolean remove(Object o) {
            boolean b = super.remove(o);
            if(b)
                orderMap.remove(o);
            return b;
        }
    }

对于测试：

public static void main(String[] str){
        ConcurrentSkipListSet set  = new ConcurrentInsertionOrderSet(new ConcurrentHashMap());
        set.add("d");
        set.add("b");
        set.add("a");
        set.add("c");
        set.add("b");
        set.add("c");
        set.add("g");
        System.out.println(set);
        set.remove("b");
        System.out.println(set);
        set.remove("c");
        set.add("c");
        System.out.println(set);
    }

输出是一个很好且一致的：
[d、b、a、c、g]
[d、a、c、g]
[d, a, g, c]

但我猜 @axel22 对竞争条件的担忧仍然存在。