有限，自動丟棄，不堵塞，併發收集

Question

我正在尋找一個集合：

• 是Deque/List - 即支持插入在「頂部」元素（最新項目去頂部） - deque.addFirst(..)/list.add(0, ..)。它可能是Queue，但迭代順序應該相反 - 即最近添加的項目應該排在第一位。
• 是有界的 - 即，具有由20個項目
• 自動丟棄最老的項目（那些「在底部」，首先加入）當達到容量
• 無阻塞的限制 - 如果雙端隊列爲空，檢索不應該阻止。它也不應該阻止/返回false/null/throw異常是deque已滿。
• 併發 - 多線程應該能夠操作它

我可以把LinkedBlockingDeque和它包裝成我的自定義集合，在add操作檢查大小和丟棄的最後一個項目（一個或多個）。有更好的選擇嗎？

Answer 1

我做這個簡單的imeplementation：

public class AutoDiscardingDeque<E> extends LinkedBlockingDeque<E> { 

    public AutoDiscardingDeque() { 
     super(); 
    } 

    public AutoDiscardingDeque(int capacity) { 
     super(capacity); 
    } 

    @Override 
    public synchronized boolean offerFirst(E e) { 
     if (remainingCapacity() == 0) { 
      removeLast(); 
     } 
     super.offerFirst(e); 
     return true; 
    } 
} 

我的需要這個就足夠了，但它應該是一個阻塞雙端隊列的語義依然遵循着高於addFirst/offerFirst不同的證據充分的方法。

Answer 2

我相信你要找的是一個有界的堆棧。沒有一個核心庫類能夠做到這一點，所以我認爲這樣做的最好方法是獲取一個非同步堆棧（LinkedList）並將其包裝在一個同步集合中，該集合會自動拋棄並在空的時候返回null流行。類似這樣的：

import java.util.Iterator; 
import java.util.LinkedList; 

public class BoundedStack<T> implements Iterable<T> { 
    private final LinkedList<T> ll = new LinkedList<T>(); 
    private final int bound; 

    public BoundedStack(int bound) { 
     this.bound = bound; 
    } 

    public synchronized void push(T item) { 
     ll.push(item); 
     if (ll.size() > bound) { 
      ll.removeLast();     
     } 
    } 

    public synchronized T pop() { 
     return ll.poll(); 
    } 

    public synchronized Iterator<T> iterator() { 
     return ll.iterator(); 
    } 
} 

...根據需要添加像isEmpty這樣的方法，如果您希望它實現例如List。

Answer 3

最簡單和經典的解決方案是覆蓋最老元素的有界環形緩衝區。

實現相當簡單。您需要一個AtomicInteger/Long for index + AtomicReferenceArray，並且您有一個無鎖通用堆棧，僅有兩種方法offer/poll，no size()。大多數併發/無鎖結構有w/size（）的困難。非覆蓋堆棧可以具有O（1），但是具有put上的分配。

東西沿着線：

package bestsss.util; 

import java.util.concurrent.atomic.AtomicLong; 
import java.util.concurrent.atomic.AtomicReferenceArray; 

public class ConcurrentArrayStack<E> extends AtomicReferenceArray<E>{ 
    //easy to extend and avoid indirections, 
    //feel free to contain the ConcurrentArrayStack if feel purist 


    final AtomicLong index = new AtomicLong(-1); 

    public ConcurrentArrayStack(int length) { 
     super(length); //returns   
    } 

    /** 
    * @param e the element to offer into the stack 
    * @return the previously evicted element 
    */ 
    public E offer(E e){ 
     for (;;){ 
      long i = index.get(); 
      //get the result, CAS expect before the claim 
      int idx = idx(i+1); 
      E result = get(idx); 

      if (!index.compareAndSet(i, i+1))//claim index spot 
       continue; 

      if (compareAndSet(idx, result, e)){ 
       return result; 
      } 
     } 
    } 

    private int idx(long idx){//can/should use golden ratio to spread the index around and reduce false sharing 
     return (int)(idx%length()); 
    } 

    public E poll(){ 
     for (;;){ 
      long i = index.get(); 
      if (i==-1) 
       return null; 

      int idx = idx(i); 
      E result = get(idx);//get before the claim 

      if (!index.compareAndSet(i, i-1))//claim index spot 
       continue; 

      if (compareAndSet(idx, result, null)){ 
       return result; 
      } 
     } 
    } 
} 

最後音符：具有模操作 是一個昂貴和功率爲2的容量是優選的，經由&length()-1（也守衛VS長溢出）。

Answer 4

這是一個處理併發並且永不返回Null的實現。 「

import com.google.common.base.Optional; 

import java.util.Deque; 
import java.util.concurrent.ConcurrentLinkedDeque; 
import java.util.concurrent.locks.ReentrantLock; 

import static com.google.common.base.Preconditions.checkArgument; 
import static com.google.common.base.Preconditions.checkNotNull; 

public class BoundedStack<T> { 
    private final Deque<T> list = new ConcurrentLinkedDeque<>(); 
    private final int maxEntries; 
    private final ReentrantLock lock = new ReentrantLock(); 

    public BoundedStack(final int maxEntries) { 
     checkArgument(maxEntries > 0, "maxEntries must be greater than zero"); 
     this.maxEntries = maxEntries; 
    } 

    public void push(final T item) { 
     checkNotNull(item, "item must not be null"); 

     lock.lock(); 
     try { 
     list.push(item); 
     if (list.size() > maxEntries) { 
      list.removeLast(); 
     } 
     } finally { 
     lock.unlock(); 
     } 
    } 

    public Optional<T> pop() { 
     return Optional.fromNullable(list.poll()); 
    } 

    public Optional<T> peek() { 
     return Optional.fromNullable(list.peekFirst()); 
    } 

    public boolean empty() { 
     return list.isEmpty(); 
    } 
}