尋找一個無界的，基於隊列，並實現爲java.util.Set

的

我正在尋找java.util.Set中的實現，具有以下特點：尋找一個無界的，基於隊列，並實現爲java.util.Set

絕不應該是並行的同步鎖定;所以很明顯，我不想使用Collections.synchronizedSet（）。
應保持廣告訂單。所以ConcurrentSkipListSet並不可取，因爲它使用compareTo（）作爲equals（），並且要求提供Comparable或Comparator的實現。還有一個ConcurrentLinkedHashMap儘管是LinkedHashMap，但不保留廣告訂單。
應該是無界的。
建議使用FIFO鏈表，因爲我的操作只對隊列的第一個元素完成。

至於我能找到的唯一正確IMPL是CopyOnWriteArraySet，但該文件中指出：

可變操作（添加，設置，刪除，等），因爲它們價格昂貴通常需要複製整個底層陣列。

在我的情況下，我有很多插入到隊列（集合）結束和很多從隊列頭部刪除（和讀取）。那麼，有什麼建議？

來源

2011-08-17 Mohsen

我想你可能不得不實施你自己的。 –

「保持插入順序」聽起來不像集合。你確定你想要一個Set而不是一個Queue嗎？ –

嗯，這不是一個普遍的需求嗎？ – Mohsen

以下解決方案在移除時存在爭用條件。它的行爲與標準的JDK集實現有所不同。

但是，它使用標準的JDK對象，並且是一個簡單的實現。只有你可以決定這種競賽條件是否可以接受，或者你是否願意投入時間找到/實施沒有比賽的解決方案。

public class FifoSet<T> 
{ 
    private ConcurrentHashMap<T,T> _map; 
    private ConcurrentLinkedQueue<T> _queue; 

    public void add(T obj) 
    { 
     if (_map.put(obj,obj) != null) 
      return; 
     _queue.add(obj); 
    } 

    public T removeFirst() 
    { 
     T obj = _queue.remove(); 
     _map.remove(obj); 
     return obj; 
    } 
}

一些更多的解釋：ConcurrentHashMap僅僅存在是爲在ConcurrentLinkedList保護;其方法put()本質上是一個比較和交換。因此，在添加到隊列中之前，請確保在地圖中沒有任何內容，並且在從隊列中移除之前不要從地圖中刪除。

刪除時的競爭條件是，將項目從隊列中移出並將其從地圖中刪除後會有一段時間。在那段時間內，添加會失敗，因爲它仍然認爲該項目在隊列中。

這是一個相對較小的競爭條件。從遠離隊列的項目到實際執行項目之間的時間差距遠沒有那麼重要。

來源

2011-08-17 17:47:49 parsifal

這兩種方法都需要鎖定。 – Mohsen

@Mohsen - 你是說當前代碼需要添加鎖，還是你在談論ConcurrentHashMap和ConcurrentLinkedQueue中固有的鎖？如果前者，答案是否定的。如果是後者，答案是「祝你好運」。 – parsifal

對不起，你是對的。調用put-add和remove-remove的順序是有用的。我正在談論你的兩種方法的鎖。順便說一句，你能解釋更多關於removeFirst方法的競爭條件。它何時發生？ – Mohsen

尋找一個無界的，基於隊列，並實現爲java.util.Set

回答

相關問題