如何实现一个并发的集合，保持插入顺序

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);
    }

但是看起来这个比较器失败了，因为集合打印出来的是：
[b, c, a, b, d]。如果b出现两次，那么它就不是一个集合了。
还有其他的替代方案吗？

- VGDIV

---

这个问题的答案是那位在 https://dev59.com/t1XTa4cB1Zd3GeqPzCxO 上提问的人所寻求的。 - mark-cs

Answer 1

您定义了一个不遵循全序属性的比较器。对于两个对象，要么其中一个小于另一个，要么另一个小于第一个。

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

由于您正在实例化一个没有指定集合中元素类型的ConcurrentSkipListSet，除非使用强制转换，否则将难以定义比较器。但是，如果您创建一个new ConcurrentSkipListSet<String>，定义比较器将更容易，因为您将知道您的对象是字符串。

- axel22

---

我正在尝试将自然排序属性（即字符串的升序）改为插入顺序。那么也许会有这样一个问题，是否可能进行这样的改装？ - VGDIV

如果您想保留插入顺序，可以使用其他并发数据结构，例如并发队列。使用并发跳表也是可能的，只需保持全局计数器，并使用CAS增加其值，并将其值写入在插入元素之前的元素中。然而问题是，您会失去线性化属性 - 在“盖章”对象和插入之间的时间内，其他人可能会向列表中插入另一个对象。我认为，如果不修改conc-skip-lists的内部结构，这非常困难或不可能。 - axel22

如上面的评论所描述的那样，你可以追踪对象的创建顺序，但不一定能追踪插入顺序。也许你需要的是前者... - axel22

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[]{}));
}

嘿，我说这不是很美观...

- Asaf

---

你说得对，如果是后期改装，那就是后期改装。我修改了（并在此发布）这个解决方案，使其也适用于删除操作。 - VGDIV

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对于竞态条件的担忧仍然存在。

- VGDIV