直接访问数据结构的Java

问题描述：

的数据结构永远只能延长（我只在尾部添加的东西）
我需要能够保持跟踪哪些元素我已经看到了（我有一个索引，理想情况下我希望能够从这个特定元素再次遍历列表）
我希望读取永远不会被阻塞，新的元素只有永远lo ck队列的尾部而不是整个队列

这是一个被多个线程严重修改的结构。

什么是最好的数据结构呢？

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

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

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

Vectors这将解决我的大部分问题，以允许某些不会抛出并发修改异常并允许直接访问的内容。但是，由于所有方法都是同步的，与阵列列表相比，性能差。鉴于我只想扩展结构，而不是在中间插入记录，所以我不愿意选择这个重量级的解决方案，读取时也会受到性能影响（但是，由于我的用例，元素的索引从来没有真正改变，因此没有必要同步读取不是尾）

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

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

您可以使用java.util.Vector而不是ArrayList。这将解决您的同步问题。 – sk2212 2013-04-25 09:34:08

+1为您的研究努力。 – 2013-04-25 09:35:06

@ user1018513你的意思是“我需要能够跟踪我已经看到的元素”。你能否多解释一下？ – Eugene 2013-04-25 09:36:03

答

CopyOnWriteArrayList结构可以解决您的问题（java.util.concurrent）。因为所有可变操作是通过创建列表的副本实现

CopyOnWriteArrayList s是线程安全的。
避免了ConcurrentModificationException的问题，因为数组在重复时不会改变。所谓的snapshot style iterator在创建迭代器时使用对数组状态的引用。
如果读取次数多于写入次数，请使用CopyOnWriteArrayList，否则使用Vector。
Vector为每个操作引入了一个小的同步延迟，当CopyOnWriteArrayList有更长的写入延迟（由于复制）但读取没有延迟。
Vector当您迭代它时需要显式同步（所以写操作不能同时执行），CopyOnWriteArrayList不需要。

鉴于该问题提供细节，它可能是最好的，如果你对你的解答扩大解释为什么它符合标准。 – 2013-04-25 09:35:49

“带有同步解决方案的向量”？ – rajesh 2013-04-25 09:36:59

拥有大量的写入，我怀疑写入时复制将是一个很好的技术。但是，一如往常，只有当你衡量它时你才会知道。 – hertzsprung 2013-04-25 09:38:38

答

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

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

答

由于sk2212表示，我认为java.util.Vector符合你的三点。

载体可以通过使用该方法add，这在列表的末尾添加元素进行扩展。
向量具有方法get(index)来检索特定索引处的具体元素。
载体是线程安全的：java Vector and thread safety http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

PLZ还补充说，因为同步的将是相当缓慢 – Eugene 2013-04-25 09:44:46

我用向量担心的是，因为所有的方法都是同步的，他们比数组列表招致不可忽略的性能开销。因为我从来没有真正去（从延长它拆开）修改阵列的内部似乎是一个重量级的解决方案。 – user1018513 2013-04-25 09:44:49

检查此链接查看Vector的VS ArrayList的http://www.javacodegeeks.com/2010/08/java-best-practices-vector-arraylist.html – 2013-04-25 09:47:45

答

这非常听起来像是你将需要一个distruptor或用简单的话无锁队列。我希望我可以在这里添加一个例子，但我只是在昨天才开始工作。我也可以告诉你它是如何工作的，或者你可以在这里阅读更好的解释：

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

LMAX

的表现看起来真的很酷... – sk2212 2013-04-25 11:47:24

答

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 ;

所有你需要做的就是定义配置对象，并小心编写相应的构造函数。

希望这对你有所帮助。

答

我要献上ConcurrentSkipListSet，因为：

1）它的并发。

2）这是一个Set。

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

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

答

看着这个，我来到@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(); 
    } 
}

答

您是否必须使用单一数据结构？如果你使用两个 - 列表中的“活动”部分，而另一个用于“你看过的项目”列表？您可以使用Vector作为“活动”部分，并使用某种管理器定期将项目移动到“您看过的项目”列表。

直接访问数据结构的Java

相关推荐