java - 可直接访问的数据结构 Java

Question

我有以下情况:

1. 一种只能永远扩展的数据结构(I only ever在尾部添加东西)
2. 我需要能够跟踪我已经拥有的元素见过(我有一个索引，理想情况下我希望能够开始从这个特定元素再次遍历列表)
3. 我希望读取永远不会阻塞，并添加新元素只锁定队列的尾部而不是整个队列

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

最好的数据结构是什么？

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

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

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

vector 这将解决我的大部分问题，即允许不会引发并发修改异常并允许直接访问的东西。但是，鉴于所有方法都是同步的，与数组列表相比，性能较差。鉴于我只想扩展结构，而不是在中间插入记录，我不愿意采用这种重量级的解决方案，其中读取也会受到性能影响(鉴于我的用例，元素的索引从来没有真正改变过，所以不需要同步不是尾部的读取)

自定义数据结构:保留我要存储的对象的数组和指向该数组尾部(最后一个元素集)的指针，插入新对象时，锁定尾部并尾部指向的物体。当对象超过其当前大小时，进行锁定调整大小操作。

最佳策略/其他更有效的实现方式是什么？

Answer 1

CopyOnWriteArrayList结构可以解决您的问题(java.util.concurrent)。

• CopyOnWriteArrayLists 是线程安全的，因为所有可变操作都是通过创建列表的副本来实现的。

• 避免了ConcurrentModificationException的问题，因为数组在迭代时不会改变。所谓的snapshot style iterator在创建迭代器时使用了对数组状态的引用。

• 如果你的读多于写，使用CopyOnWriteArrayList，否则使用Vector。

• Vector 为每个操作引入了一个小的同步延迟，而 CopyOnWriteArrayList 写入延迟较长(由于复制)但读取没有延迟。

• Vector 在迭代时需要显式同步(因此不能同时执行写操作)，CopyOnWriteArrayList 不需要。