直接訪問數據結構的Java

Question

我有以下情況：

1. 的數據結構永遠只能延長（我只 在尾部添加的東西）
2. 我需要能夠保持跟蹤哪些元素我已經看到了 （我有一個索引，理想情況下我希望能夠從這個特定元素再次遍歷列表）
3. 我希望讀取永遠不會被阻塞， 新的元素只有永遠lo ck隊列的尾部而不是 整個隊列

這是一個被多個線程嚴重修改的結構。

什麼是最好的數據結構呢？

ArrayList。這可以直接訪問使用索引看到的最後一個元素，但這會導致併發修改異常。我可以使它同步，但希望避免鎖定（或除了最後一個元素之外的任何鎖定，因爲它是唯一一個可能會同時寫入以添加新元素的地方）

ConcurrentLinkedQueue。這將解決我的併發問題，但存在的問題是我必須存儲迭代的當前位置而不是整數索引。這具有返回弱一致的迭代器這是不保證返回已添加到列表中，因爲迭代器創建（來源：javadoc的）新對象的問題

ConcurrentHashMap的與索引鍵。這樣做的好處是我可以直接訪問與正確索引對應的數據，但存在的問題是沒有「getNext」運算符，這將使我可以有效地遍歷從索引到索引+1的元素，等等。

Vectors這將解決我的大部分問題，以允許某些不會拋出併發修改異常並允許直接訪問的內容。但是，由於所有方法都是同步的，與陣列列表相比，性能差。鑑於我只想擴展結構，而不是在中間插入記錄，所以我不願意選擇這個重量級的解決方案，讀取時也會受到性能影響（但是，由於我的用例，元素的索引從來沒有真正改變，因此沒有必要同步讀取不是尾）

自定義數據結構：保持我要存儲對象的數組和指針數組的尾部（最後一個元素設置），當插入一個新對象時，鎖定尾部和尾部指向的對象。當對象超出其當前大小時，執行到鎖定大小調整操作。

什麼是最好的戰略/任何其他更有效的實施？

Answer 1

CopyOnWriteArrayList結構可以解決您的問題（java.util.concurrent）。因爲所有可變操作是通過創建列表的副本實現

• CopyOnWriteArrayList s是線程安全的。

• 避免了ConcurrentModificationException的問題，因爲數組在重複時不會改變。所謂的snapshot style iterator在創建迭代器時使用對數組狀態的引用。

• 如果讀取次數多於寫入次數，請使用CopyOnWriteArrayList，否則使用Vector。

• Vector爲每個操作引入了一個小的同步延遲，當CopyOnWriteArrayList有更長的寫入延遲（由於複製）但讀取沒有延遲。

• Vector當您迭代它時需要顯式同步（所以寫操作不能同時執行），CopyOnWriteArrayList不需要。

Answer 2

的ArrayList。這可以直接訪問使用索引看到的最後一個元素，但這會導致併發修改異常。我可以使它同步，但是想避免鎖定（或者除了最後一個元素之外的任何鎖定，因爲它是唯一一個可能會同時寫入以添加新元素的地方）

您可以使用臨時List來放置要添加的對象，當讀取事件解除阻塞時，將tmpList的內容添加到ArrayList。

Answer 3

由於sk2212表示，我認爲java.util.Vector符合你的三點。

1. 載體可以通過使用該方法add，這在 列表的末尾添加元素進行擴展。
2. 向量具有方法get(index)來檢索特定索引處的具體元素。
3. 載體是線程安全的：java Vector and thread safetyhttp://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Answer 4

這非常聽起來像是你將需要一個distruptor或用簡單的話無鎖隊列。我希望我可以在這裏添加一個例子，但我只是在昨天才開始工作。我也可以告訴你它是如何工作的，或者你可以在這裏閱讀更好的解釋：

一般的想法是，這是完全無鎖的，它只使用CAS寄存器（在java AtomicXXX中）。我只是愛上了這個想法。

LMAX

Answer 5

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 ; 

所有你需要做的就是定義配置對象，並小心編寫相應的構造函數。

希望這對你有所幫助。

Answer 6

我要獻上ConcurrentSkipListSet，因爲：

1）它的併發。

2）這是一個Set。

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

這給了你很大的靈活性，其中很多你可能不需要。但除了「你不能添加已經存在的項目」（我不知道是一個問題還是一個恩惠），它似乎滿足你所有的要求。

Answer 7

看着這個，我來到@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(); 
    } 
} 

Answer 8

您是否必須使用單一數據結構？如果你使用兩個 - 列表中的「活動」部分，而另一個用於「你看過的項目」列表？您可以使用Vector作爲「活動」部分，並使用某種管理器定期將項目移動到「您看過的項目」列表。