Looking for an unbounded, queue-based, concurrent implementation of java.util.Set

I'm looking for an implementation of java.util.Set with the following features:

1. Should be concurrent by no means of synchronized locking; So it's obvious that I don't want to use Collections.synchronizedSet().
2. Should keep insertion order. So ConcurrentSkipListSet is not preferable, because it uses compareTo() as equals(), and r开发者_JAVA百科equires to provide either an implementation of Comparable or Comparator. There is also a ConcurrentLinkedHashMap which in spite of LinkedHashMap, doesn't keep insertion order.
3. Should be unbounded.
4. Recommended be a FIFO linked list, as my operations are done only to the first element of the queue.

As far as I could find the only proper impl is CopyOnWriteArraySet, but it states in the documentation that:

Mutative operations (add, set, remove, etc.) are expensive since they usually entail copying the entire underlying array.

In my case, I have lots of insertions to the end of queue (set) and lots Any deletions (and read) from head of the queue. So, any recommendation?

The following solution has a race condition on removal. It also behaves somewhat differently from standard JDK Set implementations.

However, it uses standard JDK objects, and is a simple implementation. Only you can decide whether this race condition is acceptable, or whether you're willing to invest the timee to find/implement a solution without races.

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

Some more explanation: the ConcurrentHashMap exists solely as a guard on the ConcurrentLinkedList; its put() method is essentially a compare-and-swap. So you ensure that you don't have anything in the map before adding to the queue, and you don't remove from the map until you remove from the queue.

The race condition on remove is that there's a space of time between removing the item from the queue and removing it from the map. In that space of time, add will fail, because it still thinks the item is in the queue.

This is imo a relatively minor race condition. One that's far less important than the gap in time between removing the item from the queue and actually doing something with that item.