可直接访问的数据结构Java

Question

我有以下情况:

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

这是一个由多个线程严重修改的结构.

什么是最好的数据结构？

ArrayList.这对于能够直接访问使用索引看到的最后一个元素是理想的,但它会导致并发修改异常.我可以使它同步,但希望避免锁定(或任何锁定与最后一个元素分开,因为它是唯一一个可能有并发写入添加新元素的元素)

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

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

向量这将解决我的大多数问题,允许不会抛出并发修改异常并允许直接访问的东西.但是,鉴于所有方法都是同步的,与arraylists相比,性能较差.鉴于我只想扩展结构,而不是在中间插入记录,我不愿意采用这种重量级解决方案,其中读取也会受到性能损失(而且,考虑到我的用例,元素的索引)从来没有真正改变,因此不需要同步不是尾部的读取)

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

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

Answer 1

该的CopyOnWriteArrayList结构可以解决你的问题(java.util.concurrent中).

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

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

• 如果您有更多的读取而不是写入,请使用CopyOnWriteArrayList,否则使用Vector.

• Vector每次操作都会引入一个小的同步延迟,当CopyOnWriteArrayList写入延迟较长时(由于复制)但没有读取延迟.

• Vector在迭代它时需要显式同步(因此不能同时执行写操作),CopyOnWriteArrayList否则.