Java并发: choose synchronized collection

Question

我想同时做接下来的事情:

1. 在集合末尾添加新项目(经常)
2. 从集合开始时删除项目(或少数项目)(经常)
3. 从集合中间删除项目(或少数项目)(很少，通过迭代所有项目发生)

问题:哪个并发收集会给我最好的性能。

编辑:(如何从中间删除)

我将迭代整个集合，找到 begIndex 并删除从 begIndex 开始的 n 个下一个元素。

Answer 1

您描述的数据结构听起来完全像一个队列。 Java 为此提供了 ConcurrentLinkedQueue。

1. 添加新的集合结尾:queue.add，时间复杂度为 O(1)
2. 删除:queue.poll O(1)
3. 从任意位置移除:移除 O(n)

更多相关信息

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html

它指出

This implementation employs an efficient "wait-free" algorithm based on one described in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.