Looking for an unlimited, queue-based collaborative implementation of java.util.Set

Question

I am looking for an implementation of java.util.Set with the following functions:

• Must be parallel without synchronization; Therefore, it is obvious that I do not want to use Collections.synchronizedSet ().
• Must keep the insertion order. Therefore, ConcurrentSkipListSet is not preferred because it uses compareTo () as equals () and requires either a Comparable or Comparator implementation. There is also a ConcurrentLinkedHashMap which, despite the LinkedHashMap, does not preserve the insertion order.
• Must be unlimited.
• It is recommended to be associated with the FIFO list, since my operations are performed only for the first element of the queue.

As far as I could find, the only correct imp is CopyOnWriteArraySet , but the documentation states that:

Mutual operations (add, install, delete, etc.) are expensive because they usually entail copying the entire base array.

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

Answer 1

The following solution has a race condition on deletion. It also behaves slightly differently than standard JDK Set implementations.

However, it uses standard JDK objects and is a simple implementation. Only you can decide if this condition of the race is acceptable, or if you want to invest time 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; } } 

One more explanation: ConcurrentHashMap exists only as protection on ConcurrentLinkedList ; its put() method is essentially a comparison and a replacement. This way, you will make sure that you do not have anything on the card before adding to the queue, and you do not delete the card until you remove it from the queue.

The race condition when deleting is the time interval between removing an item from the queue and deleting it from the map. During this period of time, the addition will not be performed because it still considers that the item is in the queue.

This is a relatively minor race condition. One that is far less important than the length of time between removing an item from the queue and actually doing something with that item.