并发集队列

queue collections concurrency java set

2022-09-01 06:14:42

也许这是一个愚蠢的问题，但我似乎找不到一个明显的答案。

我需要一个仅包含唯一值的并发 FIFO 队列。尝试添加队列中已存在的值会忽略该值。如果不是线程安全，这将是微不足道的。Java中是否有数据结构，或者互联网络上的代码截图表现出这种行为？

答案 1

如果你想要比完全同步更好的并发性，我知道有一种方法可以做到这一点，使用 ConcurrentHashMap 作为后备映射。以下仅为草图。

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()

注意：此代码在一些地方使用番石榴。

答案 2

没有内置集合可以执行此操作。有一些并发实现可以与并发一起使用。SetQueue

例如，只有在将某个项目成功添加到集合后，才会将其添加到队列中，而从队列中删除的每个项目都会从该集合中删除。在这种情况下，从逻辑上讲，队列的内容实际上是集合中的任何内容，队列仅用于跟踪订单并提供仅在 .take()poll()BlockingQueue