挿入順序を維持するコンカレントセットを実装する方法

Question

私は、挿入の順序を維持し、concururently（ConcurrentModificationExceptionをスローしないように）変更可能なSet実装が必要です。

私は自分のコンパレータと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、B、D]。そのbがそこに2回あるならば、そのセットはありません。
他の選択肢はありますか？

Answer 1

total order propertyに準拠していないコンパレータを定義しました。 2つのオブジェクトのいずれか一方が他方より小さくなければならず、他方が最初のオブジェクトよりも小さくなければなりません。

あなたの場合、オブジェクトが等しくない場合、それぞれが他のオブジェクトよりも小さくなります。

ConcurrentSkipListSetは、コレクション内の要素の型が何であるかを示す型パラメータなしでインスタンス化するため、キャストを使用しない限り、コンパレータを定義する際に問題が発生します。しかし、new ConcurrentSkipListSet<String>を作成すると、オブジェクトが文字列であることが分かるので、コンパレータを定義する方が簡単になります。

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

...それはきれいではありませんでしたと述べほとんどアサフのソリューション@使用私は、しかし、私はそれを同様に削除操作との真の保持するビットを洗練：

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、C、G]
[D、 g、c]

しかし、私は競合状態に関する@ axel22の懸念がまだあると思う。