有限，自动丢弃，不堵塞，并发收集

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(); 
    } 
}