How to implement a concurrent Set that maintains insertion order

I am in the need of a Set implementation that will let me maintain insertion order and still be concuurently modifiable (as in not throw ConcurrentModificationException).

I tried using ConcurrentSkipListSet with my own comparator - sample code:

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

But it appears this comparator is a #fail because the set prints:

[b, c, a, b, d] . Its no set if b's in there twice.

Are there any other alternatives I should look at?

You've defined a comparator that does not abide the total order property. For two objects, either should one be smaller than the other, or the other smaller than the first.

In your case, if the objects are not equal, then each is smaller than the other.

Since you're instantiating a ConcurrentSkipListSet without any type parameters saying what the type of the elements in the collection will be, you'll have troubles defining the comparator unless you use casting. But if you create a new ConcurrentSkipListSet<String>, it will be easier to define the comparator, as you will know that your objects are strings.

You can define a comparator which will keep the insertion order of the strings and use that, it won't be pretty but since the comparator is always called for each new element all you need to do is something like this:

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

Hey, I said it wasn't pretty...

I pretty much used @Asaf's solution, however I refined it a bit to hold true with remove operations as well:

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

And for Test:

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

Output is a nice and consistent:
[d, b, a, c, g]
[d, a, c, g]
[d, a, g, c]

But I guess @axel22 's concern about race condition still holds.