Java中不同类型的线程安全集

Question

似乎有很多不同的实现和方法在Java中生成线程安全的集合.一些例子包括

1)CopyOnWriteArraySet

2)Collections.synchronizedSet(Set set)

3)ConcurrentSkipListSet

4)Collections.newSetFromMap(new ConcurrentHashMap())

5)以类似于(4)的方式生成的其他集合

这些示例来自Java 6中的并发模式:并发集实现

有人可以简单解释这些例子和其他例子的差异,优点和缺点吗？我无法理解并保持Java Std Docs中的所有内容.

Answer 1

1)这CopyOnWriteArraySet是一个非常简单的实现 - 它基本上有一个数组中的元素列表,当更改列表时,它复制数组.此时运行的迭代和其他访问继续使用旧数组,避免了读取器和写入器之间同步的必要性(尽管写入本身需要同步).通常快速设置操作(特别是contains())在这里非常慢,因为将在线性时间内搜索数组.

仅将此用于非常小的集合,这些集合将经常读取(迭代)并且很少更改.(Swings监听器集将是一个示例,但这些并不是真正的集合,并且应该仅在EDT中使用.)

2)Collections.synchronizedSet将简单地围绕原始集的每个方法包装一个synchronized块.您不应直接访问原始集.这意味着集合中没有两个方法可以同时执行(一个将阻塞直到另一个完成) - 这是线程安全的,但如果多个线程真正使用该集合,则不会有并发性.如果使用迭代器,在修改迭代器调用之间的集合时,通常仍需要在外部进行同步以避免ConcurrentModificationExceptions.性能将类似于原始集的性能(但具有一些同步开销,并且如果同时使用则阻塞).

如果您的并发性较低,并且希望确保所有更改对其他线程立即可见,请使用此选项.

3)ConcurrentSkipListSet是并发SortedSet实现,大多数基本操作都在O(log n)中.它允许并发添加/删除和读取/迭代,其中迭代可能会或可能不会告诉自迭代器创建以来的更改.批量操作只是多次单个调用,而不是原子操作 - 其他线程可能只观察其中的一些.

显然,只有在元素上有一些总订单时才可以使用它.这看起来是高并发情况的理想候选者,对于不太大的集合(因为O(log n)).

4)对于ConcurrentHashMap(和派生自它的集合):这里大多数基本选项(平均来说,如果你有一个好的和快速的hashCode())在O(1)(但可能退化为O(n)),就像HashMap/HashSet的.写入的并发性有限(表是分区的,写访问将在所需的分区上同步),而读访问与自身和写线程完全并发(但可能还没有看到当前更改的结果)书面).迭代器可能会也可能看不到自创建以来的更改,并且批量操作不是原子操作.调整大小很慢(对于HashMap/HashSet),因此尝试通过估计创建时所需的大小来避免这种情况(并且使用大约1/3,因为它在3/4完整时调整大小).

当您拥有大型集合,良好(和快速)散列函数时可以使用此函数,并且可以在创建映射之前估计集合大小和所需的并发性.

5)在这里可以使用其他并发地图实现吗？

Answer 2

通过使用和替换每个修改的整个集合,可以将contains()性能HashSet与并发相关的属性结合起来.CopyOnWriteArraySetAtomicReference<Set>

实施草图:

public abstract class CopyOnWriteSet<E> implements Set<E> {

    private final AtomicReference<Set<E>> ref;

    protected CopyOnWriteSet( Collection<? extends E> c ) {
        ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
    }

    @Override
    public boolean contains( Object o ) {
        return ref.get().contains( o );
    }

    @Override
    public boolean add( E e ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( current.contains( e ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.add( e );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

    @Override
    public boolean remove( Object o ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( !current.contains( o ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.remove( o );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

}

Answer 3

如果Javadocs没有帮助,你可能应该找一本书或文章来阅读有关数据结构的内容.乍看上去:

• 每次改变集合时,CopyOnWriteArraySet都会生成基础数组的新副本,因此写入速度很慢,迭代器快速且一致.
• Collections.synchronizedSet()使用old-school synchronized方法调用来创建Set threadsafe.这将是一个低性能版本.
• ConcurrentSkipListSet提供具有不一致批处理操作(addAll,removeAll等)和迭代器的高性能写入.
• Collections.newSetFromMap(新的ConcurrentHashMap())具有ConcurrentHashMap的语义,我认为它不一定针对读取或写入进行优化,但是像ConcurrentSkipListSet一样,具有不一致的批处理操作.