并发设置队列 [英] Concurrent Set Queue
问题描述
也许这是一个愚蠢的问题,但我似乎找不到一个明显的答案。
Maybe this is a silly question, but I cannot seem to find an obvious answer.
我需要一个并发的FIFO队列,只包含唯一的值。尝试添加已存在于队列中的值将忽略该值。其中,如果不是为了线程安全将是微不足道的。在Java中有一个数据结构,或者是在具有这种行为的网络上的代码snipit?
I need a concurrent FIFO queue that contains only unique values. Attempting to add a value that already exists in the queue simply ignores that value. Which, if not for the thread safety would be trivial. Is there a data structure in Java or maybe a code snipit on the interwebs that exhibits this behavior?
推荐答案
如果你想要更好的并发比完全同步,有一种方式我知道做,使用ConcurrentHashMap作为背景图。以下是仅草图。
If you want better concurrency than full synchronization, there is one way I know of to do it, using a ConcurrentHashMap as the backing map. The following is a sketch only.
public final class ConcurrentHashSet<E> extends ForwardingSet<E>
implements Set<E>, Queue<E> {
private enum Dummy { VALUE }
private final ConcurrentMap<E, Dummy> map;
ConcurrentHashSet(ConcurrentMap<E, Dummy> map) {
super(map.keySet());
this.map = Preconditions.checkNotNull(map);
}
@Override public boolean add(E element) {
return map.put(element, Dummy.VALUE) == null;
}
@Override public boolean addAll(Collection<? extends E> newElements) {
// just the standard implementation
boolean modified = false;
for (E element : newElements) {
modified |= add(element);
}
return modified;
}
@Override public boolean offer(E element) {
return add(element);
}
@Override public E remove() {
E polled = poll();
if (polled == null) {
throw new NoSuchElementException();
}
return polled;
}
@Override public E poll() {
for (E element : this) {
// Not convinced that removing via iterator is viable (check this?)
if (map.remove(element) != null) {
return element;
}
}
return null;
}
@Override public E element() {
return iterator().next();
}
@Override public E peek() {
Iterator<E> iterator = iterator();
return iterator.hasNext() ? iterator.next() : null;
}
}
这种方法不是阳光。除了使用后台映射的 entrySet()。iterator()。next()
,我们没有正确的方法来选择头元素,结果是映射获得更多更不平衡,随着时间的推移。
All is not sunshine with this approach. We have no decent way to select a head element other than using the backing map's entrySet().iterator().next()
, the result being that the map gets more and more unbalanced as time goes on. This unbalancing is a problem both due to greater bucket collisions and greater segment contention.
注意:此代码使用几个地方的Guava 。
这篇关于并发设置队列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!