直接可访问的数据结构Java
我有以下情况：
- 一个只能扩展的数据结构（我只能在尾部添加东西）
- 我需要能够跟踪我已经看到了哪些元素（我有一个索引，理想情况下，我想能够从这个特定的元素开始遍历列表）
- 我希望读取永不被阻塞，并添加新的元素只locking队列的尾部，而不是整个队列
这是一个由多个线程严重修改的结构。
什么是最好的数据结构呢？
ArrayList 。 这将是理想的能够直接访问使用索引看到的最后一个元素，但它会导致并发修改exception。 我可以使它同步，但希望避免locking（或从最后一个元素除外的任何locking，因为它是唯一可能有并发写入添加新元素）
ConcurrentLinkedQueue 。 这将解决我的并发问题，但有问题，我将不得不存储迭代的当前位置，而不是一个整数索引。 这有一个问题，即它返回一个弱一致的迭代器，它不能保证从迭代器创build以来已经添加到列表中的新对象（source：javadoc）
以索引作为关键字的ConcurrentHashMap 。 这样做的好处是我可以直接访问与正确索引相对应的数据，但是有一个问题，就是没有一个“getNext”操作符，它允许我有效地遍历索引到索引+1等元素
vector这将解决我的大部分问题，允许一些不会抛出并发修改exception，并允许直接访问。 但是，由于所有方法都是同步的，与arrays列表相比，性能差。 鉴于我只想扩展结构，而不是在中间插入logging，所以我不愿意去做这个重量级的解决scheme，在这个解决scheme中，读取也会受到性能的影响（但是，由于我的用例，元素的索引从来没有真正改变，所以没有必要同步读取不是尾巴）
自定义数据结构 ：保存一个我想存储的对象的数组和一个指向这个数组尾部的指针（最后一个元素集），当插入一个新的对象时，locking尾部和尾部指向的对象。 当对象超出当前大小时，执行locking大小调整操作。
什么是最好的战略/更有效的实施？
CopyOnWriteArrayList结构可以解决你的问题（java.util.concurrent）。
-
CopyOnWriteArrayList是线程安全的，因为所有的可变操作都是通过创build列表副本来实现的。 -
ConcurrentModificationException的问题可以避免，因为数组在迭代时不会改变。 所谓的snapshot style iterator器在创buildsnapshot style iterator使用对数组状态的引用。 -
如果读取比写入更多，则使用
CopyOnWriteArrayList，否则使用Vector。 -
当
CopyOnWriteArrayList具有较长的写入延迟（由于复制），但读取没有延迟时，向每个操作引入一个小的同步延迟。 -
Vector在迭代时需要显式同步（所以写操作不能同时执行），CopyOnWriteArrayList不会。
看着这个，我来到@MissingNumber相同的解决scheme。
使用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(); } }
这听起来很像你需要一个破坏者，或者简单地说，locking空闲队列。 我希望能在这里增加一个例子，但是我昨天才开始工作。 我也可以告诉你它是如何工作的，或者你可以在这里阅读更好的解释：
一般的想法是，这是完全无锁的，它只使用CAS寄存器（在java AtomicXXX中）。 我只是爱上了这个想法。
LMAX
正如sk2212所说，我认为java.util.Vector符合你的三点。
- 可以使用方法
add来扩展向量，这会在列表的末尾添加元素。 - 向量具有方法
get(index)来检索特定索引处的具体元素。 - 向量是线程安全的： java向量和线程安全 http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html
以索引作为键的ConcurrentHashMap可以解决你的问题，但是你需要做更多的工作来做到这一点。
就像下面的伪代码一样。
Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >(); class ConfiguredObject { YourObject Object;// the object which you want to map for map[key]; ConfiguredObject Next;//the object which you want to map for map[key+1]; ConfiguredObject Previous;//the object which you want to map for map[key-1]; YourObject NextObject; YourObject PrevObject; }
所以这应该解决你所有的问题。
并发性框架照顾。
索引键是您的索引。
迭代 ，用这个代码，如果你有索引，你可以使用
myMap.get(key).Next ; myMap.get(key).Previous ;
所有你需要做的就是定义可configuration的对象，并相应地写入构造函数。
希望这对你有所帮助。
数组列表。 这将是理想的能够直接访问使用索引看到的最后一个元素，但它会导致并发修改exception。 我可以使它同步，但要避免locking（或从最后一个元素除外的任何locking，因为它是唯一可能有并发写入添加新元素）
您可以使用一个临时List来放置要添加的对象，并在读取事件解除阻塞时，将tmpList的内容添加到ArrayList中。
我将提供ConcurrentSkipListSet ，因为：
1）它是并发的。
2）这是一个Set 。
3）它也是NavigableSet ，因此也是一个SortedSet 。
这给了你很大的灵活性，其中大部分你可能不需要。 但除了“你不能添加已经存在的项目”（我不知道是一个问题还是一个恩惠），它似乎满足你所有的要求。
你必须使用单一的数据结构吗？ 如果你使用二进制作为列表的“主动”部分，而另一个用于“已经看过的项目”列表呢？ 您可以使用Vector作为“活动”部分，也可以使用某种定期将项目移动到“已看过的项目”列表的pipe理器。
