11.5.4　数据结构

java. util.concurrent包中也提供了一些适合多线程程序使用的高性能数据结构，包括队列和集合类对象等。

1.队列

队列是多线程程序中比较常用的一种数据结构。多个线程对同一个队列进行操作，通过队列来进行数据传递。java.util.concurrent包中的BlockingQueue接口表示的是线程安全的阻塞式队列。BlockingQueue接口本身封装了生产者-消费者场景所需的语义。当队列已满时，向队列中添加数据的方法会阻塞当前线程；当队列已空时，从队列中获取数据的方法会阻塞当前线程。使用BlockingQueue接口可以非常容易地实现生产者-消费者场景，只需要让生产者和消费者线程共享一个BlockingQueue接口的实现对象，并分别调用不同的方法即可。线程之间的具体同步机制由BlockingQueue接口的实现类负责处理。BlockingQueue接口中的方法支持阻塞式和非阻塞式两种方式。阻塞式的方式通过put方法向队列添加数据，通过take方法从队列中获取数据。非阻塞方式则分别通过offer和poll方法来完成。Java标准库中提供的BlockingQueue接口的实现包括基于数组的固定元素个数的ArrayBlockingQueue类和基于链表结构的不固定元素个数的LinkedBlockingQueue类。开发人员可以根据需要选择合适的实现类。

与BlockingQueue接口功能相似的是BlockingDeque接口，不过BlockingDeque接口表示的是可以对头尾都进行添加和删除操作的双向队列。BlockingDeque接口中的方法分成两类，分别在队首和队尾进行操作。标准库中只提供了BlockingDeque接口的一种基于链表的实现—LinkedBlockingDeque类。

BlockingQueue和BlockingDeque接口的实现类都是阻塞式队列。如果队列中所包含的元素数量没有限制，可以使用ConcurrentLinkedQueue和ConcurrentLinkedDeque类。这两个类在实现中使用了非阻塞式算法，避免了使用锁机制，性能比较好。

2.集合类

另外一部分实用的Java类是线程安全的集合类。在多线程程序中，如果共享变量是集合类的对象，则不适合直接使用java.util包中已有的集合类。这些集合类有些不是线程安全的，有些在多线程环境下性能比较差。更好的选择是使用java.util.concurrent包中的集合类。

当需要使用散列表时，可以使用ConcurrentMap接口的实现类。ConcurrentMap接口继承自java.util.Map接口，增添了几个方法。这几个方法虽然包含了条件判断，但都是原子操作。调用者不需要考虑同步的问题。其中putIfAbsent方法只有在散列表中不包含给定的键时，才会把给定的值放入散列表中；remove方法在散列表中包含给定键和值的条目时，删除该条目；replace方法有两种重载形式，第一种形式是在散列表中包含给定的键时，用指定的新值替换原来的值，另外一种形式是在调用时需要指定键、期望的旧值和要设置的新值。当散列表中给定键对应的值与期望的旧值相等时，用给定的新值进行替换。这种形式的replace方法的含义相当于compareAndSet方法。

ConcurrentMap接口的基本实现是ConcurrentHashMap类。在创建Concurrent-HashMap类的对象时，一般使用默认的不带任何参数的构造方法。不过考虑到ConcurrentHashMap在多线程程序中的性能问题，如果可以预先估算一些数值，那么可以提高ConcurrentHashMap的使用性能。第一个要考虑的因素是ConcurrentHashMap类的对象中可能包含的条目个数。因为在ConcurrentHashMap类的实现中动态调整所能包含的条目数量的操作比较耗时，如果可以事先指定一个相对合理的初始大小，那么可以避免不必要的调整大小的操作。第二个要考虑的因素是同时进行更新操作的线程数。ConcurrentHashMap类在实现中会根据这个估计的线程数把内部的空间划分成对应数量的部分。从理论上来说，这些线程可以分别在不同的部分同时进行更新操作，而不会互相冲突。如果设置的线程数过大或过小，会对性能造成一定的影响。如果不显式指定，那么使用的默认值是16。这个默认值对某些场景来说是不合适的。比如，在很多情况下，只有一个线程进行更新操作，其他线程只进行读取操作，这时把值设为1可以提高性能。

需要注意的是，ConcurrentHashMap类的对象在使用时，读取操作和更新操作可能会重叠在一起。比如，putAll方法会把一组条目添加到散列表中。在完成对某一个条目的添加之后，并发进行的读取操作就可以获取新添加的条目，此时putAll方法可能还在进行其他条目的添加操作。通过ConcurrentHashMap接口的方法可以获取散列表中包含的键和值的集合。当从这些集合中创建出迭代器对象之后，迭代器对象只与集合保持弱一致性。通过迭代器可以访问在其创建时集合中包含的元素，但是不一定可以反映出迭代器创建之后散列表所发生的变化。在使用迭代器的方法时不会抛出java.util.ConcurrentModificationException异常。

如果需要在多线程程序中使用java.util.List接口的实现类，可以使用CopyOnWrite-ArrayList类。在CopyOnWriteArrayList类的实现中，所有对列表的更新操作都会重新创建一个底层数组的副本，并使用这个副本来存储数据。对列表的更新操作是加锁的，而读取操作是不加锁的。通过复制的方式避免了可能产生的数据竞争，但是带来了额外的开销。一般对List接口的读取操作要多于更新操作，因此采用这种方式是比较合理的。如果在使用中发现对List接口实现对象的更新操作相对较多，则不适合使用CopyOnWriteArrayList类。通过CopyOnWriteArrayList类的iterator方法得到的迭代器对象只反映迭代器创建时列表的状态。如果在创建迭代器之后，对CopyOnWriteArrayList类的对象进行了更新操作，在更新之后，CopyOnWriteArrayList类的对象使用了新的底层数组，而之前创建的迭代器仍然引用的是旧的底层数组。