ConcurrentHashMap Collections.synchronizedMap和Hashtable讨论

[转]http://www.w3china.org/blog/more.asp?name=hongrui&id=37960

在Java类库中出现的第一个关联的集合类是Hashtable，它是JDK1.0的一部分。Hashtable提供了一种易于使用的、线程安全的、关联的map功能，这当然也是方便的。然而，线程安全性是凭代价换来的――Hashtable的所有方法都是同步的。此时，无竞争的同步会导致可观的性能代价。Hashtable的后继者HashMap是作为JDK1.2中的集合框架的一部分出现的，它通过提供一个不同步的基类和一个同步的包装器Collections.synchronizedMap，解决了线程安全性问题。

通过将基本的功能从线程安全性中分离开来，Collections.synchronizedMap允许需要同步的用户可以拥有同步，而不需要同步的用户则不必为同步付出代价。Hashtable和synchronizedMap所采取的获得同步的简单方法（同步Hashtable中或者同步的Map包装器对象中的每个方法）有两个主要的不足。首先，这种方法对于可伸缩性是一种障碍，因为一次只能有一个线程可以访问hash表。同时，这样仍不足以提供真正的线程安全性，许多公用的混合操作仍然需要额外的同步。

虽然诸如get()和put()之类的简单操作可以在不需要额外同步的情况下安全地完成，但还是有一些公用的操作序列，例如迭代或者put-if-absent（空则放入），需要外部的同步，以避免数据争用。有条件的线程安全性同步的集合包装器synchronizedMap和synchronizedList，有时也被称作有条件地线程安全――所有单个的操作都是线程安全的，但是多个操作组成的操作序列却可能导致数据争用，因为在操作序列中控制流取决于前面操作的结果。

如果一个条目不在Map中，那么添加这个条目。不幸的是，在containsKey()方法返回到put()方法被调用这段时间内，可能会有另一个线程也插入一个带有相同键的值。如果您想确保只有一次插入，您需要用一个对Map进行同步的同步块将这一对语句包装起来。List.size()的结果在循环的执行期间可能会变得无效，因为另一个线程可以从这个列表中删除条目。可能在进入循环的最后一次迭代之后有一个条目被另一个线程删除了，则List.get()将返回null，抛出一个NullPointerException异常。那么，采取什么措施才能避免这种情况呢？如果当您正在迭代一个List时另一个线程也可能正在访问这个List，那么在进行迭代时您必须使用一个synchronized块将这个List包装起来，在List上同步，从而锁住整个List。

这样做虽然解决了数据争用问题，但是在并发性方面付出了更多的代价，因为在迭代期间锁住整个List会阻塞其他线程，使它们在很长一段时间内不能访问这个列表。集合框架引入了迭代器，用于遍历一个列表或者其他集合，从而优化了对一个集合中的元素进行迭代的过程。然而，在java.util集合类中实现的迭代器极易崩溃，也就是说，如果在一个线程正在通过一个Iterator遍历集合时，另一个线程也来修改这个集合，那么接下来的Iterator.hasNext()或Iterator.next()调用，会抛出ConcurrentModificationException异常。

如果想要防止出现ConcurrentModificationException异常，那么当您正在进行迭代时，您必须使用一个在Listl上同步的synchronized块将该List包装起来，从而锁住整个List。（也可以调用List.toArray()，在不同步的情况下对数组进行迭代，但是如果列表比较大的话这样做代价很高）。

而ConcurrentHashMap是DougLea的util.concurrent包的一部分，现已被集成到JDK5.0中,它提供比Hashtable或者synchronizedMap更高程度的并发性。而且，对于大多数成功的get()操作它会设法避免完全锁定，其结果就是使得并发应用程序有着非常好的吞吐量。

1 针对吞吐量进行优化

ConcurrentHashMap使用了几个技巧来获得高程度的并发以及避免锁定，包括为不同的hashbucket（桶）使用多个写锁和使用JMM的不确定性来最小化锁被保持的时间——或者根本避免获取锁。对于大多数一般用法来说它是经过优化的，这些用法往往会检索一个很可能在map中已经存在的值。事实上，多数成功的get()操作根本不需要任何锁定就能运行。（警告：不要自己试图这样做！想比JMM聪明不像看上去的那么容易。util.concurrent类是由并发专家编写的，并且在JMM安全性方面经过了严格的同行评审。）

2 多个写锁

我们可以回想一下，Hashtable（或者替代方案Collections.synchronizedMap）的可伸缩性的主要障碍是它使用了一个map范围（map-wide）的锁，为了保证插入、删除或者检索操作的完整性必须保持这样一个锁，而且有时候甚至还要为了保证迭代遍历操作的完整性保持这样一个锁。这样一来，只要锁被保持，就从根本上阻止了其他线程访问Map，即使处理器有空闲也不能访问，这样大大地限制了并发性。

ConcurrentHashMap摒弃了单一的map范围的锁，取而代之的是由32个锁组成的集合，其中每个锁负责保护hashbucket的一个子集。锁主要由变化性操作（put()和remove()）使用。具有32个独立的锁意味着最多可以有32个线程可以同时修改map。这并不一定是说在并发地对map进行写操作的线程数少于32时，另外的写操作不会被阻塞——32对于写线程来说是理论上的并发限制数目，但是实际上可能达不到这个值。但是，32依然比1要好得多，而且对于运行于目前这一代的计算机系统上的大多数应用程序来说已经足够了。

3 map范围的操作

有32个独立的锁，其中每个锁保护hashbucket的一个子集，这样需要独占访问map的操作就必须获得所有32个锁。一些map范围的操作，比如说size()和isEmpty()，也许能够不用一次锁整个map（通过适当地限定这些操作的语义），但是有些操作，比如map重排（扩大hashbucket的数量，随着map的增长重新分布元素），则必须保证独占访问。Java语言不提供用于获取可变大小的锁集合的简便方法。必须这么做的情况很少见，一旦碰到这种情况，可以用递归方法来实现。

4 JMM概述

在进入put()、get()和remove()的实现之前，让我们先简单地看一下JMM。JMM掌管着一个线程对内存的动作（读和写）影响其他线程对内存的动作的方式。由于使用处理器寄存器和预处理cache来提高内存访问速度带来的性能提升，Java语言规范（JLS）允许一些内存操作并不对于所有其他线程立即可见。有两种语言机制可用于保证跨线程内存操作的一致性——synchronized和volatile。

按照JLS的说法，“在没有显式同步的情况下，一个实现可以自由地更新主存，更新时所采取的顺序可能是出人意料的。”其意思是说，如果没有同步的话，在一个给定线程中某种顺序的写操作对于另外一个不同的线程来说可能呈现出不同的顺序，并且对内存变量的更新从一个线程传播到另外一个线程的时间是不可预测的。

虽然使用同步最常见的原因是保证对代码关键部分的原子访问，但实际上同步提供三个独立的功能——原子性、可见性和顺序性。原子性非常简单——同步实施一个可重入的（reentrant）互斥，防止多于一个的线程同时执行由一个给定的监视器保护的代码块。不幸的是，多数文章都只关注原子性方面，而忽略了其他方面。但是同步在JMM中也扮演着很重要的角色，会引起JVM在获得和释放监视器的时候执行内存壁垒（memorybarrier）。

一个线程在获得一个监视器之后，它执行一个读屏障（readbarrier）——使得缓存在线程局部内存（比如说处理器缓存或者处理器寄存器）中的所有变量都失效，这样就会导致处理器重新从主存中读取同步代码块使用的变量。与此类似，在释放监视器时，线程会执行一个写屏障（writebarrier）——将所有修改过的变量写回主存。互斥独占和内存壁垒结合使用意味着只要您在程序设计的时候遵循正确的同步法则（也就是说，每当写一个后面可能被其他线程访问的变量，或者读取一个可能最后被另一个线程修改的变量时，都要使用同步），每个线程都会得到它所使用的共享变量的正确的值。