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

问题

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

1)CopyOnWriteArraySet

2)Collections.synchronizedSet(Set set)

3)ConcurrentSkipListSet

4)Collections.newSetFromMap(new ConcurrentHashMap())

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

这些例子来自Concurrency Pattern: Concurrent Set implementations in Java 6

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


#1 热门回答(169 赞)

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

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

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

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

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

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

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

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

5)在这里可以使用其他并发 Map 实现吗?


#2 热门回答(18 赞)

可以使用AtomicReference<Set>HashSet的性能与1308673571的并发相关属性组合在一起,并在每次修改时替换整个集合。

实施草图:

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

}

#3 热门回答(10 赞)

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

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