4

次の機能を備えた java.util.Set の実装を探しています。

  1. 同期ロックを使用しないで同時実行する必要があります。したがって、 Collections.synchronizedSet ()を使用したくないことは明らかです。
  2. 広告掲載順を維持する必要があります。したがって、ConcurrentSkipListSet は、compareTo() を equals() として使用し、Comparable または Comparator の実装を提供する必要があるため、好ましくありません。LinkedHashMap にもかかわらず、挿入順序を保持しないConcurrentLinkedHashMapもあります。
  3. 無制限にする必要があります。
  4. 私の操作はキューの最初の要素に対してのみ行われるため、FIFO リンク リストをお勧めします。

私が見つけた限り、唯一の適切な実装はCopyOnWriteArraySetですが、ドキュメントには次のように記載されています。

ミュータティブ操作 (追加、設定、削除など) は、通常、基になる配列全体をコピーする必要があるため、コストがかかります。

私の場合、キューの最後に多くの挿入（セット）があり、キューの先頭から多くの削除（および読み取り）があります。それで、何かお勧めはありますか？

4

1 に答える 1

6

次のソリューションには、削除時に競合状態があります。また、標準の JDK Set 実装とは動作が多少異なります。

ただし、標準の JDK オブジェクトを使用しており、単純な実装です。この競合状態が許容できるかどうか、または競合のないソリューションを見つけて実装するために時間を費やす意思があるかどうかを判断できるのは、あなただけです。

public class FifoSet<T>
{
    private ConcurrentHashMap<T,T> _map;
    private ConcurrentLinkedQueue<T> _queue;

    public void add(T obj)
    {
       if (_map.put(obj,obj) != null)
          return;
       _queue.add(obj);
    }

    public T removeFirst()
    {
       T obj = _queue.remove();
       _map.remove(obj);
       return obj;
    }
}

もう少し説明: はConcurrentHashMap、 のガードとしてのみ存在しConcurrentLinkedListます。そのput()方法は本質的に比較と交換です。したがって、キューに追加する前にマップに何もないことを確認し、キューから削除するまでマップから削除しません。

削除時の競合状態は、アイテムをキューから削除してからマップから削除するまでに時間の間隔があることです。その時間のスペースでは、アイテムがまだキューにあると見なされるため、追加は失敗します。

これは、比較的マイナーな競合状態です。アイテムをキューから削除してから実際にそのアイテムで何かを行うまでの時間のギャップよりもはるかに重要ではありません。

于 2011-08-17T17:47:49.467 に答える