Java集合框架详解：多线程存储与并发数据处理

前言

我们常说程序就是数据结构和算法的结合，可见数据结构在编程概念中是多么的重要。我们在编写应用程序过程中常常涉及到的是对一组数据的处理就是将多个数据放到一起作为一个整体来对其进行操作处理。为此，Java为我们提供了一个Java集合框架(JCF)专门来规范集合数据的定义和操作。

先是Collection，Iterator等接口规定了对群体数据的基本操作，然后将数据封装到Set，List，Map等类型的集合中。然后探讨了能否存在重复数据，需不需要排序，键值对形式存储，还是地址指针连接，为了快速查找创建哈希索引等问题。

多线程中集合处理

到了多线程并发编程中，我们要在多线程并发环境下操作这些数据集，就必须要考虑对这些数据集的线程安全问题了。

其实在我们日常编程过程中，我们已经使用过很多线程安全的集合类型了。只是我们可能没有注意到而已。所谓的集合线程安全其实就是针对集合数据的操作方法都需要是同步的，比如类Hashtable和Vector是此类的例子。作为JDK 1.0版以来的一部分，这些基本数据结构的设计考虑到了线程安全。这里的线程安全性只意味着所有方法都是在实例级同步。

类似像如下操作方法的定义：

public synchronized void clear(){Entry tab[] = table;modCount++;for(int index = tab.length; --index >=0;)tab[index] = null;count = 0;}

现在我们可以通过一些方法将非线程安全的集合创建成线程安全的，比如

HashMap map = new HashMap();Map synchronizedMap = Collections.synchronizedMap(map);

正如我们在上面的代码中看到的，Collections类允许我们在运行时将创建的以前非同步的Collections转变为该类的同步版本。

我们前面介绍同步机制说过，给方法添加synchronized关键字会让方法在每个时间点上只能有一个线程执行。

当然，这是使简单集合类线程安全的最简便的方法。还有更高级的实现技术，比如为并发访问设计的特殊算法。

关于ConcurrentHashMap

我们的java.util.concurrent包中，就包含了不少对这些特殊算法的实现类。

比如ConcurrentHashMap：

ConcurrentHashMap map = new ConcurrentHashMap();map.put(key,value);String value2 = map.get(key);

上面的代码看起来与普通HashMap几乎相同，但是底层实现完全不同。

ConcurrentHashMap不再为整个表使用一个锁，而是将整个表细分为许多小分区。每个分区都有自己的锁。

因此，假设从不同的线程在表的不同分区上编写操作，那么从不同的线程向这个Map写入操作不会相互竞争，并且可以使用它们自己的锁。

该实现还引入了提交写操作的思想，以减少读操作的等待时间。

这稍微改变了读操作的语义，因为它将返回已完成的最新写操作的结果。

我们简单可以一下其源代码定义片段：

其中，

concurrencyLevel是并发级别定义并发更新线程的估计数量，其实现试着调整适应内部执行的并发访问的线程数量

loadFactor是负载因子则是一个阈值，用于控制该集合扩展大小。

initialCapacity是初始容量，实现执行内部空间大小以能够容纳该数量的元素。

通常，ConcurrentHashMap被划分为许多段，我们将每个分段作为同步单元。

ConcurrentHashMap有一个名为Segment的内部final类，我们可以定义这个分段数组长度，比如我们取32，那么我们可以说ConcurrentHashMap在内部被划分为大小为32的段，也就是说每次最多可以运行32个线程。

这意味着在高并发性期间，每个线程可以在每个分段上工作，最多32个线程可以在max上运行，max仅维护32个锁来保护ConcurrentHashMap的每个哈希bucket。

简单比较测试

为了更好地了解Hashtable、同步的HashMap和ConcurrentHashMap的不同性能，让我们实现一个简单的性能测试。

下面的代码启动几个线程，让每个线程在一个随机位置从Map中检索一个值，然后在另一个随机位置更新一个值:

这里我们定义了一个执行时间统计函数runPerfTest，然后分别用普通的Hashtable，同步处理的HashMap以及我们java.util.concurrent包中定义的专用集合类作为容器进行填数操作。

执行结果如下：

正如我们所期望的，Hashtable和同步的HashMap实现远远落后于并发包。

注意这里我们还使用了一个ConcurrentSkipListMap，它是HashMap的一个跳转列表实现，其中一个bucket内的链接项形成一个跳转列表，这意味着列表已排序，列表中有不同级别的链接项。最高级别的指针直接指向列表中间的某个项。如果该项已经大于当前项，迭代器必须使用下一个较低级别的链接，以跳过比最高级别更少的元素。

关于跳转列表有趣的一点是，所有读访问都需要大约log(n)的时间，即使所有项都存储在同一个bucket中。也就是说其哈希值是相同的的元素链表。

总结

在我们多线程并发编程中，处理集合数据需要注意同步锁对性能的影响，为此我们一般情况下不会考虑将真个集合数据加同步锁，而是采用java.util.concurrent包中提供的相关集合类定义比如,ConcurrentHashMap是在HashMap数据集基础上进行了特殊处理的集合类，它允许并发的访问底层map数据集，在这个数据结构中，将map分为多个成为片段(Segment)内部数据结构，将它作为被同步锁定的单元。

在我们向该类型Map添加或者更新该Map的数据时，相关的片段会被锁定，而不是将整个Map表锁定。同时它允许非锁定状态下多个线程并发访问其值。通过这种同步内部数据片段结构的方式，大大提高了访问性能。