43

我有以下情况：

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

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

最好的数据结构是什么？

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

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

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

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

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

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

4

8 回答 8

11

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

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

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

  • 如果您的读取次数多于写入次数，请使用CopyOnWriteArrayList，否则使用Vector。

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

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

于 2013-04-25T09:35:08.813 回答
4

这听起来很像您需要一个干扰器，或者简单地说是无锁队列。我希望我可以在这里添加一个示例，但我昨天才开始研究它。我还可以告诉你它是如何工作的，或者你可以在这里阅读更好的解释：

一般的想法是这是完全无锁的，它只使用 CAS 寄存器（在 java AtomicXXX 中）。我只是爱上了这个想法。

最大

于 2013-04-25T09:40:46.420 回答
4

对此进行调查，我得出了与@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();
  }
}
于 2013-04-25T15:34:37.043 回答
1

正如sk2212所说，我认为java.util.Vector符合你的三点。

  1. 可以使用 方法扩展向量，该方法add在列表末尾添加元素。
  2. 向量具有get(index)在特定索引处检索具体元素的方法。
  3. 向量是线程安全的：java 向量和线程安全 http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html
于 2013-04-25T09:40:12.343 回答
1

以索引为键的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 ;

您需要做的就是定义可配置对象并相应地编写构造函数。

希望这对您有所帮助。

于 2013-04-25T11:08:41.037 回答
0

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

您可以使用临时列表来放置要添加的对象，当读取的内容解除阻塞时，您可以将 tmpList 的内容添加到 ArrayList。

于 2013-04-25T09:36:45.533 回答
0

我将提供 up ConcurrentSkipListSet，因为：

1）它是并发的。

2) 它是一个Set.

3) 它也是NavigableSet，因此也是SortedSet。

这为您提供了很大的灵活性，其中大部分您可能不需要。但除了“你不能添加已经存在的项目”（我不知道这是一个问题还是一个恩惠）之外，它似乎满足了你的所有要求。

于 2013-04-25T14:11:50.037 回答
0

你必须使用单一的数据结构吗？如果您使用两个 - 一个用于列表的“活动”部分，一个用于“您已看到的项目”列表，该怎么办？您可以将 Vector 用于“活动”部分，并使用某种管理器定期将项目移动到“您已经看到的项目”列表中。

于 2013-05-01T15:45:32.497 回答