Thread-safe finding and deleting an object from a collection
I wonder how I can do something like the following
class MyCollection<E> implements Collection<E> {
@Nullable E findAndRemove(Predicate<E> predicate) {
for (E e : this) {
if (predicate.test(e)) {
remove(e);
return e;
}
}
return null;
}
}
in thread safe mode. It really shouldn't be Collection
, since the only operations needed are add
and findAndRemove
. note that
-
removeIf
irrelevant as it removes all matched elements and returns nothing - let's say the sync isn't good enough
-
CopyOnWriteArrayList
can do, but the Javadoc says "efficient when ... traversal operations are vastly superior to mutations", which is definitely not the case here. - it is not allowed to return the same element twice (unless re-added), which can easily happen when used
CopyOnWriteArrayList
naively - which returns the match item is irrelevant.
Concerning premature optimization and XY problem: Yes, I know! I got into this when I was fooling myself with something I might or might not need in one day, but I find this problem interesting as such.
source to share
Since you only need the add
and methods findAndRemove
, some type of parallel hash is a natural choice as there has been a good implementation of ( ConcurrentHashMap
) since Java 1.5. Now, since we don't really need it Map
, but rather Set
, we can just use (since Java 8) ConcurrentHashMap.newKeySet()
to create a parallel set using the same implementation as the parallel map.
Then, given the parallel set, we can pretty much use your loop above and optimistically remove the item, and then just continue searching on failure (meaning the thread simultaneously removed the item that matched):
class MyCollection<E> {
private Set<E> underlying = ConcurrentHashMap.newKeySet();
void add(E elem) {
underlying.add(elem);
}
@Nullable E findAndRemove(Predicate<E> predicate) {
for (E e : underlying) {
if (predicate.test(e) && remove(e)) {
return e;
}
}
return null;
}
}
The only real change with regard to your example code is that we check the result Set.remove()
to see if the item has actually been removed. For parallel dialing, this works "safely"; Only the thread that actually deletes the object will see true
, so this set will correctly return the item only if it was actually deleted, in which case no other thread will be able to return that item.
It should satisfy all your requirements and do, as well as the main parallel map implementations, which are "very good" on modern JDKs.
Note that use Set
implies that duplicate elements are not allowed. It was not clear from your description if you plan to support duplicates or not, but if you did, you could use the same approach built on a parallel multimap 1 or simply using ConcurrentHashMap<E, AtomicInteger>
where the value AtomicInteger
indicates the number of references to the number of elements with the same same key, methods add
and findAndRemove
handle reference count 2 .
1 However, on a quick search, I could not find an obvious open source parallel multiplex implementation. Note that you don't really need a capital-M implementation Multimap
with all its features - you really only need a "multiple multinet" with the ability to add an item, iterate over the available items, and "remove" an item (i.e., reduce it to set).
2 I am actually hiding a few details of the referencing implementation, since in this case there is a possible race between a thread that decreases the refcount to zero and any thread calling add
for the same element that can increment the recount above zero (but the entry has already been deleted). This can be avoided, but I am not going into details as it is unclear if you want to support duplicates.
source to share