Java理论与实践: 构建一个更好的HashMap[Java编程]

ConcurrentHashMap 是 Doug Lea的 util.concurrent 包的一部份,它供应 比Hashtable 大概 synchronizedMap 更高程度的并发性.并且,关于大大都成 功的 get() 操作它会设法避免完好锁定,后来果就是使得并发利用程序有着非 常好的吞吐量.这个月,BrianGoetz 细心解析了 ConcurrentHashMap的代码, 并探究 Doug Lea 是如安在不丧失线程安全的情形下获得这么骄人成就的.

在7月份的那期 Java理论与实践（“ Concurrent collections classes”） 中,我们简单地回想了可伸缩性的瓶颈,并谈论了怎么用同享数据构造的办法获 得更高的并发性和吞吐量.有时刻学习的最好办法是解析专家的成果,所以这个 月我们将解析 Doug Lea的 util.concurrent 包中的 ConcurrentHashMap的实现 .JSR 133 将指定 ConcurrentHashMap的一个版本,该版本针对 Java 内存模子 （JMM）作了优化,它将包含在JDK 1.5的 java.util.concurrent 包中. util.concurrent 中的版本在老的和新的内存模子中都已通过线程安全考核.

针对吞吐量举行优化

ConcurrentHashMap 利用了几个本领来得到高程度的并发以及避免锁定,包 括为差别的 hash bucket（桶）利用多个写锁和利用 JMM的不肯定性来最小化锁 被保持的时间――大概根本避免获得锁.关于大大都普通用法来说它是经过优化 的,这些用法常常会检索一个极大概在map 中已经存在的值.事实上,大都成功 的 get() 操作根本不需求任何锁定就可以运行.（告诫:不要自己试图这样做! 想比 JMM 聪明不像看上去的那么简单. util.concurrent 类是由并发专家编写 的,并且在JMM 安全性方面经过了严峻的同行评审.）

多个写锁

我们可以回想一下,Hashtable（大概替换筹划 Collections.synchronizedMap ）的可伸缩性的主要障碍是它利用了一个 map 范围（map-wide）的锁,为了保证插入、删除大概检索操作的完好性必须保持这 样一个锁,并且有时刻乃至还要为了保证迭代遍历操作的完好性保持这样一个锁 .这样一来,只要锁被保持,就从根本上禁止了其他线程拜候 Map,即便处理器 有闲暇也不能拜候,这样大大地限制了并发性.

ConcurrentHashMap 摒弃了单一的 map 范围的锁,取而代之的是由 32 个锁 构成的调集,此中每个锁负责保护 hash bucket的一个子集.锁主要由改变性操 作（ put() 和remove() ）利用.具有 32 个独立的锁意味着最多可以有 32 个 线程可以同时改正 map.这并不一定是说在并发地对 map 举行写操作的线程数 少于 32 时,别的的写操作不会被阻塞――32 关于写线程来说是理论上的并发 限制数目,但是实际上大概达不到这个值.但是,32 仍然比 1 要好得多,并且 关于运行于目前这一代的计算机系统上的大大都利用程序来说已经充足了.  

map 范围的操作

有 32 个独立的锁,此中每个锁保护 hash bucket的一个子集,这样需求独 占拜候 map的操作就必须得到全部32个锁.一些 map 范围的操作,比方说 size() 和isEmpty(), 也答应以不用一次锁整个 map（通过适本地限定这些操 作的语义）,但是有些操作,比方 map 重排（扩大 hash bucket的数目,随着 map的增长重新分布元素）,则必须保证独占拜候.Java 语言不供利用于获得可 变大小的锁调集的简便办法.必须这么做的情形很少见,一旦碰到这种情形,可 以用递归办法来实现.

JMM概述

在进入 put() 、 get() 和remove()的实现之前,让我们先简单地看一下 JMM.JMM 掌管着一个线程对内存的行动（读和写）影响其他线程对内存的行动 的方法.由于利用处理器存放器和预处理 cache 来提高内存拜候速度带来的性 能晋升,Java 语言标准（JLS）答应一些内存操作并不关于全部其他线程立便可 见.有两种语言机制可用于保证跨线程内存操作的一致性―― synchronized 和 volatile.

按照 JLS的说法,“在没有显式同步的情形下,一个实现可以安闲地更新主 存,更新时所采纳的次序大概是出其不意的.”其意思是说,假如没有同步的话 ,在一个给定线程中某种次序的写操作关于别的一个差别的线程来说大概显现出 差别的次序, 并且对内存变量的更新从一个线程转到达别的一个线程的时间是 不可猜测的.

固然利用同步最常见的缘由是保证对代码关键部份的原子拜候,但实际上同 步供应三个独立的功效――原子性、可见性温次序性.原子性非常简单――同步 实施一个可重入的（reentrant）互斥,避免多于一个的线程同时履行由一个给 定的监督器保护的代码块.不幸的是,大都文章都只关注原子性方面,而忽视了 其他方面.但是同步在JMM 中也扮演着很重要的角色,会惹起 JVM 在得到和释 放监督器的时刻履行内存壁垒（memory barrier）.

一个线程在得到一个监督器之后,它履行一个 读屏障（read barrier）―― 使得缓存在线程部分内存（比方说处理器缓存大概处理器存放器）中的全部变量 都失效,这样就会招致处理器重新从主存中读取同步代码块利用的变量.与此类 似,在释放监督器时,线程会履行一个 写屏障（write barrier）――将全部修 改过的变量写回主存.互斥独占和内存壁垒结合利意图味着只要您在程序计划的 时刻遵守精确的同步法例（也就是说,每当写一个背面大概被其他线程拜候的变 量,大概读取一个大概最后被另一个线程改正的变量时,都要利用同步）,每个 线程城市得到它所利用的同享变量的精确的值.

假如在拜候同享变量的时刻没有同步的话,就会发生一些奇特的事情.一些 改变大概会通过线程当即反映出来,而其他的则需求一些时间（这由关联缓存的 本质所致）.后果,假如没有同步您就不能保证内存内容一定一致（相关的变量 彼此间大概会不一致）,大概不能得到当前的内存内容（一些值大概是过期的） .避免这种危险情形的常用办法（也是举荐利用的办法）当然是精确地利用同步 .但是在有些情形下,比方说在像 ConcurrentHashMap 之类的一些利用非常广 泛的库类中,在开辟历程当中还需求一些额外的专业技术和勤奋（大概比普通的 开辟要多出很多倍）来得到较高的性能.

　　以上是“Java理论与实践: 构建一个更好的HashMap[Java编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：