面试题九：ConcurrentHashMap如何支持并发访问？

ConcurrentHashMap如何支持并发访问？

一、面试官视角：这道题想考察什么？

  • 是否熟练掌握线程安全的概念
  • 是否深入理解ConcurrentHashMap的各项并发优化的原理
  • 是否掌握锁优化的方法

二、题目剖析：

1、并发访问即考察线程安全问题

2、回答ConcurrentHashMap原理即可

3、如果你对ConcurrentHashMap的原理不了解

  • 分析下HashMap为什么不是线程安全的
  • 编写并发程序时你会怎么做，举例说明最佳
    • 保证可见性
    • 保证操作原子性
    • 禁止重排序

4、CHM的并发优化历程

​ 对于CHM的优化实质上是一个持续性的过程，从JDK1.5出现到JDK1.8之后，每个版本都没有停止过对其进行优化，甚至到JDK1.8有个特别大的改动，就是直接摒弃段。

  • JDK 5：分段锁，必要时加锁

    分段加锁，著名的segment[]，不同段之间的访问实质上不受影响

  • JDK 6：优化二次Hash算法

    针对Hash算法进行二次优化，hash算法到底优化了什么呢？首先我们看源码，hash(key)，这个key就是我们put进来的key，然后对它的hash值进行再一次的散列，拿到一个hashCode，这个值就是用于在普通的hashTable[]中找到相对应的位置，但是因为在JDK1.5中已经分段了，所以hash的值还需要用于在segment[]中找到相对应的位置，综合来说，就是先拿hash高位去segment[]中找位置，然后再用hash低位去hashTable[]中找位置，那么这个时候就要尽可能的保证segment和hashTable里面分布一定要均匀，不然的话，如果都堆到一个segment分段里面的话，你就会发现它退化成了一个hashTable，这就不合适了，所以JDK1.5存在什么问题呢？如果这个key是一个整数的话，你就会发现，它的hash值的高位对于3w多以下的整数得到的结果都是一样的，都是最后那一个segment，这样就达不到分段锁优化的目的了，而超过3w多到40w、50w的hash数值，它的高位也仍然在14到15之间，只有随着hash数值增加，高位才会慢慢的均匀分布在各个段里面，而JDK1.6对这个hash算法做了优化。

    JDK1.5：hash值对于比较小的整数（3w多以下），它的Hash高位始终是15，这样的话就没有办法均匀的分布在各个段里面，因此它会退化成一个hashTable。

    1
    2
    3
    4
    5
    6
    7
    8
    static int hash(Object x) {
     int h = x.hashCode();
     h += ~(h << 9);
     h ^= (h >>> 14);
     h += (h << 4);
     h ^= (h >>> 10);
     return h;
    }

    JDK1.6：高位低位均匀分布，因为在JDK1.6中，启用了single-word Wang/Jenkins hash

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private static int hash(int h) {
    	// single-word Wang/Jenkins hash
     h += ~(h << 15) ^ 0xffffcd7d;
     h ^= (h >>> 10);
     h += (h << 3);
     h ^= (h >>> 6);
     h += (h << 2) + (h << 14);
     return h ^ (h >>> 16);
    }

  • JDK 7：段懒加载，volatile & cas（compareAndSet）

    JDk1.7之前，Segment会直接初始化，也就是当你创建CHM时，16个Segment会统统创建出来，而从JDK1.7开始，段没有一开始就实例化了，而是需要时才会去初始化，并且访问的时候也尽可能的使用volatile & cas来避免加锁，假如此时第一个hash(key)被扔进来之后，它会放到第一个segment里面，其它的segment都不能放，因为只有使用时才会实例化，但实例化过程中会涉及到一个问题，就是segment的可见性的问题，比如ThreadA过来把这个segment实例化，ThreadB也同时过来访问这个segment的时候，有可能因为可见性的问题，访问不到这个刚刚被初始化的segment，也正是因为这一点，在JDk1.7里面，大量使用了对segment[]的volatile的一个访问，这个访问基于Unsafe类，它提供了volatile访问数组的能力，确保segment创建之后具备可见性。

  • JDK 8：摒弃段，基于HashMap原理的并发实现

    直接摒弃段，通篇都是基于HashMap的一个改造，改造了对于一些不必加锁的地方，尽量使用volatile进行访问，一些实在没有办法需要加锁的地方，比如写入的操作，也尽量选择一个很小的范围去加锁。

    JDK1.7，我们是说使用volatile访问segment[]，在JDK1.8中摒弃段（segment），直接使用volatile访问hashTable。

5、CHM如何计数

  • JDK5~7基于段元素个数求和，二次不同就加锁
  • JDK8引入CounterCell，本质上也是分段计数

6、CHM是弱一致性的

  • 添加元素后不一定马上能读到

    有可能，我添加的时候，你已经读过去了

  • 清空之后可能仍然会有元素

    我是一段一段的清，有可能我刚刚清理了这段，你又添加进来了

  • 遍历之前的段元素的变化会读到

    如果我还没有遍历到段15，我现在正在遍历段14，你在段15里面做了修改，待会我遍历到段15时就会感觉到段15发生了变化

  • 遍历之后的段元素变化读不到

    如果我遍历到了段14，但你对段13做了修改，那么我就感觉不到了

  • 遍历时元素发生变化不抛异常

    因为遍历是经常发生的

7、HashTable的问题

​ HashTable虽然是线程安全的，但是它非常的粗暴和野蛮，因为你想修改它、想读取它都需要拿锁。

  • 大锁：对HashTable对象加锁
  • 长锁：直接对方法加锁
  • 读写锁共用：只有一把锁，从头锁到尾

8、针对HashTable的问题，CHM的解法

  • 小锁：分段锁（JDK5~7），桶节点锁（JDK8）
  • 短锁：先尝试获取，失败再加锁
  • 分离读写锁：读失败再加锁（JDK5~7），volatile读、CAS（compareAndSet）写（JDK7~8）

9、如何进行锁优化？

  • 长锁不如短锁：尽可能只锁必要的部分

  • 大锁不如小锁：尽可能对加锁的对象拆分

    HashTable就是典型的大锁，它的锁是直接加到类上面的

  • 公锁不如私锁：尽可能将锁的逻辑放到私有代码中

    尽可能将锁的逻辑放到私有代码中，对外暴露的时候，其实不要让它看到锁，因为如果说外面访问的时候，让它加锁的话，可能会给它的使用带来不必要的麻烦，甚至带来一些错误，因为外部使用的时候，也许不知道你内部的一些逻辑，有可能在使用的过程中，锁不正当的使用，导致死锁也是有可能的。

  • 嵌套锁不如扁平锁：尽可能在代码设计时避免锁嵌套

    这样也能避免逻辑上出现问题，或者出现死锁的情况发生

  • 分离读写锁：尽可能将读锁和写锁分离

    因为大多数的的情况，都在读，只有少部分的时间在写，那么这个时候的话，写可能需要加一个比较重的锁，而读的话，有可能volatile就足够了，甚至不加锁也可以。

  • 粗化高频锁：尽可能合并处理频繁过短的锁

    如果你有一段代码，它被拆成了很多小段，每一小段都加了锁，那么我们知道每加一把锁，它都需要一些开销，如果你这个地方加锁和释放锁的频率特别高，那么就要考虑把它们合并到一块，减少一次性加锁的开销。

  • 消除无用锁：尽可能不加锁，或用volatile替代锁