也许这是一个愚蠢的问题,但我似乎找不到一个明显的答案.
Maybe this is a silly question, but I cannot seem to find an obvious answer.
我需要一个仅包含唯一值的并发 FIFO 队列.尝试添加队列中已经存在的值只会忽略该值.如果不是为了线程安全,那将是微不足道的.是否有 Java 中的数据结构或互联网上的代码片段表现出这种行为?
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.
Note: this code uses Guava in a few places.
更多推荐
并发集合队列
发布评论