java - FIFO 顺序固定容量的线程安全集合

Question

问题:维护一个具有固定容量(例如 2 个元素)的集合，该集合可同时跨 100 多个线程访问。

始终存储最近线程中的最新元素。存储它们后，编写一个方法来检查所有这些元素是否重复。

我的解决方案:BlockingQueue 具有固定容量并实现自定义添加方法。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.Iterator;

public class FixedBlockingQueue<T extends Object> {

    final BlockingQueue<T> queue;
    private int capacity;

    public FixedBlockingQueue(int capacity){
        super();
        this.capacity = capacity;
        queue = new ArrayBlockingQueue<T>(capacity);
        System.out.println("Capactiy:"+this.capacity);
    }
    public void addElement(T element){
        try{
            if ( queue.size() > capacity - 1 ){
                queue.remove();         
            }
            queue.put(element);
            for ( Iterator it = queue.iterator(); it.hasNext();){
                System.out.println(it.next());
            }
            System.out.println("________");
        }catch(Exception err){
            err.printStackTrace();
        }
    }

    public static void main(String args[]){
        FixedBlockingQueue<Integer> f = new FixedBlockingQueue<Integer>(2);
        for ( int i=0; i< 10; i++){
            f.addElement(i);
        }

    }   
}

输出:

0
________
0
1
________
1
2
________
2
3
________
3
4
________
4
5
________
5
6
________
6
7
________
7
8
________
8
9

从输出中，您可以清楚地看到第一个元素被删除，最近的元素被添加到队列中。

我的疑问:这是好的解决方案吗？或者有没有其他更好的解决方案，比这个更好？

编辑:在这种频繁删除的场景下，ArrayBlockingQueue 是否优于 LinkedBlockingQueue？

Answer 1

让我们避免重新发明轮子，只使用一个固定容量的LinkedBlockingQueue，它是一个线程安全的FIFO BlockingQueue。更多详情 here .

您的代码的问题是您不是以原子方式执行以下操作，因此您可能会遇到竞争条件问题:

if ( queue.size() > capacity - 1 ){
    queue.remove();         
}
queue.put(element);

您需要将它包装到一个synchronized block 中或使用一个明确的Lock 来保护它，因为它是一个关键部分，我们不希望多个线程调用它同时。

下面是如何使用 BlockingQueue 完成的:

BlockingQueue queue = new LinkedBlockingQueue(2);
for ( int i=0; i< 10; i++){
    // Try to add the object and return immediately if it is full
    // then if it could not be added,
    // remove the last element of the queue and try again
    while (!queue.offer(i, 0L, TimeUnit.MICROSECONDS)) {
        queue.remove();
    }
    for ( Iterator it = queue.iterator(); it.hasNext();){
        System.out.println(it.next());
    }
    System.out.println("________");
}

输出:

0
________
0
1
________
1
2
________
2
3
________
3
4
________
4
5
________
5
6
________
6
7
________
7
8
________
8
9
________