5 ConcurrentHashMap的操作
主要研究ConcurrentHashMap的3种操作——get操作、put操作和size操作.
5.1 get操作
Segment的get操作实现非常简单和高效.
- 先经过一次再散列
- 然后使用该散列值通过散列运算定位到Segment
- 最后通过散列算法定位到该元素.
public V get(Object key) { Segment<K,V> s; HashEntry<K,V>[] tab; int h = hash(key); //找到segment的地址 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; //取出segment，并找到其hashtable if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { //遍历此链表，直到找到对应的值 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);e != null; e = e.next) { K k; if ((k = e.key) == key || (e.hash == h && key.equals(k))) return e.value; } } return null; }
整个get方法不需要加锁，只需要计算两次hash值，然后遍历一个单向链表（此链表长度平均小于2），因此get性能很高;
高效之处在于整个过程不需要加锁,除非读到的值是空才会加锁重读.
HashTable容器的get方法是需要加锁的,那ConcurrentHashMap的get操作是如何做到不加锁的呢?
原因是它的get方法将要使用的共享变量都定义成了volatile型;
如用于统计当前Segement大小的count字段和用于存储值的HashEntry的value.
定义成volatile的变量,能够在线程之间保持可见性,能够被多线程同时读,并且保证不会读到过期的值,但是只能被单线程写(有一种情况可以被多线程写,就是写入的值不依赖于原值);
在get操作里只需要读不需要写共享变量count和value,所以可以不用加锁.
之所以不会读到过期的值,是因为根据Java内存模型的happen before原则,对volatile字段的写操作先于读操作;
即使两个线程同时修改和获取volatile变量,get操作也能拿到最新的值;
这是用volatile替换锁的经典应用场景.
transient volatile int count; volatile V value;
在定位元素的代码里可以发现,定位HashEntry和定位Segment的散列算法虽然一样,都与数组的长度减去1再相“与”,但是相“与”的值不一样
- 定位Segment使用的是元素的hashcode再散列后得到的值的高位
- 定位HashEntry直接使用再散列后的值.
其目的是避免两次散列后的值一样,虽然元素在Segment里散列开了,但是却没有在HashEntry里散列开.
hash >>> segmentShift & segmentMask // 定位Segment所使用的hash算法 int index = hash & (tab.length - 1); // 定位HashEntry所使用的hash算法
5.2 put操作
由于需要对共享变量进行写操作，所以为了线程安全，在操作共享变量时必须加锁。
首先定位到Segment，然后在Segment里进行插入操作。插入操作需经历两个步骤：
- 判断是否需要对Segment里的HashEntry数组进行扩容
- 定位添加元素的位置，然后将其放在HashEntry数组
1.是否需要扩容
在插入元素前会先判断Segment里的HashEntry数组是否超过容量(threshold),如果超过阈值,则对数组进行扩容.
值得一提的是,Segment的扩容判断比HashMap更恰当,因为HashMap是在插入元素后判断元素是否已经到达容量的,如果到达了就进行扩容,但是很有可能扩容之后没有新元素插入,这时HashMap就进行了一次无效的扩容.
2.如何扩容
在扩容的时候,首先会创建一个容量是原来两倍的数组,然后将原数组里的元素进行再散列后插入到新的数组。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只对某个segment扩容。
put方法的第一步，计算segment数组的索引，并找到该segment，然后调用该segment#put
public V put(K key, V value) { if (value == null) // ConcurrentHashMap 不允许 null 作为映射值 throw new NullPointerException(); int hash = hash(key.hashCode()); // 根据散列码找到对应的 Segment return segmentFor(hash).put(key, hash, value, false); }
根据 hash 值找到对应的 Segment
final Segment<K,V> segmentFor(int hash) { // 将散列值右移 segmentShift 个位，并在高位填充 0 // 然后把得到的值与 segmentMask 相“与” // 从而得到 hash 值对应的 segments 数组的下标值 // 最后根据下标值返回散列码对应的 Segment 对象 return segments[(hash >>> segmentShift) & segmentMask]; }
put方法第二步，在Segment的put方法中进行操作：
V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); // 加锁，这里是锁定某个 Segment 对象而非整个 ConcurrentHashMap try { int c = count; if (c++ > threshold) // 如果超过再散列的阈值 rehash(); // 执行再散列，table 数组的长度将扩充一倍 HashEntry<K,V>[] tab = table; // 把散列码值与 table 数组的长度减 1 的值相“与” // 得到该散列码对应的 table 数组的下标值 int index = hash & (tab.length - 1); // 找到散列码对应的具体的那个桶 HashEntry<K,V> first = tab[index]; HashEntry<K,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue; if (e != null) { // 如果键 / 值对以经存在 oldValue = e.value; if (!onlyIfAbsent) e.value = value; // 设置 value 值 } else { // 键 / 值对不存在 oldValue = null; ++modCount; // 要添加新节点到链表中，所以 modCont 要加 1 // 创建新节点，并添加到链表的头部 tab[index] = new HashEntry<K,V>(key, hash, first, value); count = c; // 写 count 变量 } return oldValue; } finally { unlock(); // 解锁 } }
注意：这里的加锁操作是针对（键的 hash 值对应的）某个具体的 Segment,锁定的是该 Segment 而不是整个 ConcurrentHashMap;
因为插入键 / 值对操作只是在这个 Segment 包含的某个桶中完成，不需要锁定整个ConcurrentHashMap;
此时，其他写线程对另外 15 个Segment 的加锁并不会因为当前线程对这个 Segment 的加锁而阻塞;
同时，所有读线程几乎不会因本线程的加锁而阻塞（除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null，此时需要加锁后重新读取该值）
相比较于 HashTable 和由同步包装器包装的 HashMap每次只能有一个线程执行读或写操作;
ConcurrentHashMap 在并发访问性能上有了质的提高;
在理想状态下,ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设置为 16）,及任意数量线程的读操作.
5.3 size操作
要统计整个ConcurrentHashMap里元素的数量,就必须统计所有Segment里元素的数量后计总;
Segment里的全局变量count是一个volatile;
在并发场景下,是不是直接把所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢?
不是的
虽然相加时可以获取每个Segment的count的最新值,但是可能累加前使用的count发生了变化,那么统计结果就不准了;
所以,最安全的做法是在统计size的时候把所有Segment的put、remove和clean方法全部锁住,但是这种做法显然非常低效.
因为在累加count操作过程中,之前累加过的count发生变化的几率非常小
所以ConcurrentHashMap的做法是先尝试2次通过不锁Segment的方式来统计各个Segment大小;
如果统计的过程中,count发生了变化,则再采用加锁的方式来统计所有Segment的大小.
那么ConcurrentHashMap又是如何判断在统计的时候容器是否发生了变化呢?
使用modCount变量,在put、remove和clean方法里操作元素前都会将变量modCount进行加1;
那么在统计size前后比较modCount是否发生变化,从而得知容器的大小是否发生变化.
6 用 Volatile 变量协调读写线程间的内存可见性
由于内存可见性问题，未正确同步的情况下，写线程写入的值可能并不为后续的读线程可见
下面以写线程 M 和读线程 N 来说明 ConcurrentHashMap 如何协调读 / 写线程间的内存可见性问题
假设线程 M 在写入了 volatile 型变量 count 后，线程 N 读取了这个 volatile 型变量 count
根据 happens-before 关系法则中的程序次序法则
- A appens-before 于 B
- C happens-before D
根据Volatile 变量法则
- B happens-before C
根据传递性，连接上面三个 happens-before 关系得到
A appens-before 于 B； B appens-before C；C happens-before D
也就是说：写线程 M 对链表做的结构性修改，在读线程 N 读取了同一个 volatile 变量后，对线程 N 也是可见的
虽然线程 N 是在未加锁的情况下访问链表;
JMM可以保证：只要之前对链表做结构性修改操作的写线程 M 在退出写方法前写 volatile 型变量 count;
读线程 N 在读取这个 volatile 型变量 count 后，就一定能“看到”这些修改
ConcurrentHashMap 中，每个 Segment 都有一个变量 count;
它用来统计 Segment 中的 HashEntry 的个数;
这个变量被声明为 volatile.
transient volatile int count;
所有不加锁读方法，在进入读方法时，首先都会去读这个 count 变量
比如下面的 get 方法：
V get(Object key, int hash) { if(count != 0) { // 首先读 count 变量 HashEntry<K,V> e = getFirst(hash); while(e != null) { if(e.hash == hash && key.equals(e.key)) { V v = e.value; if(v != null) return v; // 如果读到 value 域为 null，说明发生了重排序，加锁后重新读取 return readValueUnderLock(e); } e = e.next; } } return null; }
在 ConcurrentHashMap 中，所有执行写操作的方法（put, remove, clear），在对链表做结构性修改之后，在退出写方法前都会去写这个 count 变量
所有未加锁的读操作（get, contains, containsKey）在读方法中，都会首先去读取这个 count 变量。
根据 Java 内存模型，对 同一个 volatile 变量的写 / 读操作可以确保：写线程写入的值，能够被之后未加锁的读线程“看到”。
这个特性和前面介绍的 HashEntry 对象的不变性相结合，使得在 ConcurrentHashMap 中，读线程在读取散列表时，基本不需要加锁就能成功获得需要的值。这两个特性相配合，不仅减少了请求同一个锁的频率（读操作一般不需要加锁就能够成功获得值），也减少了持有同一个锁的时间（只有读到 value 域的值为 null 时 , 读线程才需要加锁后重读）。
7 ConcurrentHashMap 实现高并发的总结
7.1 基于通常情形而优化
在实际的应用中，散列表一般的应用场景是：除了少数插入操作和删除操作外，绝大多数都是读操作，而且读操作在大多数时候都是成功的;
正是基于这个前提，ConcurrentHashMap 针对读操作做了大量的优化;
通过HashEntry 对象的不变性和用 volatile 型变量协调线程间的内存可见性;
使得大多数时候，读操作不需要加锁就可以正确获得值;
这个特性使得 ConcurrentHashMap 的并发性能在分离锁的基础上又有了近一步的提高.
7.2 总结
ConcurrentHashMap 是一个并发散列映射表的实现，它允许完全并发的读取，并且支持给定数量的并发更新;
相比于 HashTable 和用同步包装器包装的 HashMap（Collections.synchronizedMap(new HashMap())），ConcurrentHashMap 拥有更高的并发性;
在 HashTable 和由同步包装器包装的 HashMap 中，使用一个全局的锁来同步不同线程间的并发访问;
同一时间点，只能有一个线程持有锁，也就是说在同一时间点，只能有一个线程能访问容器;
这虽然保证多线程间的安全并发访问，但同时也导致对容器的访问变成串行化的了。
在使用锁来协调多线程间并发访问的模式下，减小对锁的竞争可以有效提高并发性;
有两种方式可以减小对锁的竞争：
- 减小请求同一个锁的频率
- 减少持有锁的时间
ConcurrentHashMap 的高并发性主要来自于三个方面：
- 1.用分离锁实现多个线程间的更深层次的共享访问,减小了请求同一个锁的频率
- 2.用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求
- 3.通过对同一个 Volatile 变量的写 / 读访问，协调不同线程间读 / 写操作的内存可见性
由于散列映射表在实际应用中大多数操作都是成功的读操作，所以 2 和 3 既可以减少请求同一个锁的频率，也可以有效减少持有锁的时间
通过减小请求同一个锁的频率和尽量减少持有锁的时间 ，使得 ConcurrentHashMap 的并发性相对于 HashTable 和用同步包装器包装的 HashMap有了质的提高。
