可直接访问的数据结构 Java

data-structures concurrency java

2022-09-01 01:40:16

我有以下情况：

一个只能扩展的数据结构（我只在尾巴上添加东西）
我需要能够跟踪我已经看到的元素（我有一个索引，理想情况下，我希望能够从这个特定元素再次开始遍历列表）
我希望读取永远不会被阻塞，并且添加新元素以仅锁定队列的尾部而不是整个队列

这是一个由多个线程大量修改的结构。

为此，最好的数据结构是什么？

数组列表。这是理想的，以便能够直接访问使用索引看到的最后一个元素，但它会导致并发修改异常。我可以使它同步，但希望避免锁定（或除了最后一个元素之外的任何锁定，因为它是唯一一个可能有并发写入以添加新元素的锁定）

ConcurrentLinkedQueue.这将解决我的并发问题，但问题是我必须存储迭代的当前位置而不是整数索引。这有一个问题，它返回一个弱一致性的迭代器，不能保证返回自创建迭代器以来已添加到列表中的新对象（来源：javadoc）

具有索引作为键的 ConcurrentHashMap。这样做的好处是，我可以直接访问与正确索引对应的数据，但存在一个问题，即没有“getNext”运算符可以让我有效地遍历从索引到索引+ 1等的元素。

向量这将解决我允许不会引发并发修改异常并允许直接访问的内容的大多数问题。但是，假设所有方法都是同步的，因此与数组列表相比，性能较差。鉴于我只想扩展结构，而不是在中间插入记录，我不愿意采用这种重量级的解决方案，其中读取也会受到性能影响（而，鉴于我的用例，元素的索引实际上永远不会改变，因此无需同步不是尾部的读取）

自定义数据结构：保留一个我要存储的对象数组和一个指向此数组尾部（最后一个元素集）的指针，在插入新对象时，锁定尾部和尾部所指向的对象。当对象超过其当前大小时，进行锁定调整大小操作。

什么是最佳策略/任何其他更有效的实施？

答案 1

CopyOnWriteArrayList结构可以解决你的问题（java.util.concurrent）。

CopyOnWriteArrayLists 是线程安全的，因为所有突变操作都是通过创建列表的副本来实现的。
避免了的问题，因为数组在迭代时不会更改。所谓的在创建迭代器时使用对数组状态的引用。ConcurrentModificationExceptionsnapshot style iterator
如果读取次数多于写入次数，请使用，否则使用。CopyOnWriteArrayListVector
Vector为每个操作引入一个小的同步延迟，当写入延迟较长（由于复制）但没有读取延迟时。CopyOnWriteArrayList
Vector在迭代时需要显式同步（因此无法同时执行写入操作），不需要。CopyOnWriteArrayList

答案 2

研究这个问题，我得出了与@MissingNumber相同的解决方案。

使用 ConcurrentHashMap 作为支持数据结构：

非阻塞读取
线程安全追加

要按索引添加随机访问，请使用 AtomicInteger 来维护索引，并将其作为键来检索映射值。

public class ConcurrentListMap {

  private final ConcurrentHashMap<Integer, Object> backingMap;
  private final AtomicInteger index;

  public ConcurrentListMap() {
    backingMap = new ConcurrentHashMap();
    index = new AtomicInteger(0);
  }

  public int append(final Object value) {
    final int newIndex = index.incrementAndGet();
    backingMap.put(newIndex, value);
    return newIndex;
  }

  public Object get(final int entry) {
    return backingMap.get(entry);
  }

  public int getTailIndex() {
    return index.get();
  }
}