HashMap是最常用的键值对容器但多线程并发 put() 操作会出现数据丢失等问题是线程不安全的Hashtable 则是在所有方法上加synchronized锁住整个哈希表。这就好比大型货舱只有一把大锁。只要有一个人入库存取货物其余所有人排队等待。并发量高的时候大量线程阻塞性能极差。于是ConcurrentHashMap应运而生既能保证线程安全又不会像 Hashtable 那样串行排队。一、演化之路从“分段锁”到“CAS synchronized”JDK1.7Segment数组 HashEntry数组 单向链表把一个大的Map切成多个SegmentSegment继承了ReentrantLock。简单来说就是把一个大数组切成了 16 段默认每段配一把锁。不同段的线程互不影响。但是锁的粒度偏大内存开销也大。而且Segment 数组一旦初始化不可扩容只有 Segment 内部的 HashEntry 数组支持扩容。JDK1.8Node数组 哈希表 单向链表 红黑树哈希表为空无哈希冲突使用CAS 无锁写入不加锁有哈希冲突synchronized锁住链表头洁点 / 红黑树根节点。最大并发量等于数组长度数组长度默认为16如果链表长度 8并且数组容量 64容量小于64数组扩容链表转为红黑树节点数 6红黑树退化为链表查询复杂度由 O (n) 降到 O (logn)。二、源码剖析1 禁用null值2 初始化CAS 抢锁 (initTable)3 插入数据1无锁插入 (putVal)2synchronized锁插入4 多线程协助扩容1任务分配多个线程用 CAS 争抢全局变量transferIndex从数组尾部往前认领一段连续的数组下标。 CAS 保证同一段下标区间只会被一个线程领取不会重复干活。2头结点加锁synchronized (f) 锁住该数组下标头节点哈希表不同下标位置可以同时进行操作并发高。3链表拆分哈希表旧数组长度n是 2 的幂扩容也是2倍扩容hashn 只有两种结果hash n 0放到新数组 i位置不变低位链表 lnhash n ! 0放到新数组 in高位链表 hn4收尾所有参与扩容的线程都干完活后进入finishing阶段。完整扫一遍旧数组确认全部下标都标记了 ForwardingNode替换 table 引用为nextTab扩容生效后重置SIZECTL为新的扩容阈值。5 获取数据get()三、总结1、get()方法全程无锁依靠 volatile 保证可见性读的效率很高只有写 put / 扩容才会用到 synchronizedCAS。2、get()会读到脏数据volatile 保证可见性能读到已经完成写入的最新节点但并发场景下get 和 put 同时执行仍然存在读到旧值的并发问题读和写并发不保证原子性3、HashMap的key、value可以 nullConcurrentHashMap的key、value都不允许nullget (key) 返回 null无法区分是key不存在还是存入的value本身就是 null。4、ConcurrentHashMap适合
HashMap是最常用的键值对容器但多线程并发 put() 操作会出现数据丢失等问题是线程不安全的Hashtable 则是在所有方法上加synchronized锁住整个哈希表。这就好比大型货舱只有一把大锁。只要有一个人入库存取货物其余所有人排队等待。并发量高的时候大量线程阻塞性能极差。于是ConcurrentHashMap应运而生既能保证线程安全又不会像 Hashtable 那样串行排队。一、演化之路从“分段锁”到“CAS synchronized”JDK1.7Segment数组 HashEntry数组 单向链表把一个大的Map切成多个SegmentSegment继承了ReentrantLock。简单来说就是把一个大数组切成了 16 段默认每段配一把锁。不同段的线程互不影响。但是锁的粒度偏大内存开销也大。而且Segment 数组一旦初始化不可扩容只有 Segment 内部的 HashEntry 数组支持扩容。JDK1.8Node数组 哈希表 单向链表 红黑树哈希表为空无哈希冲突使用CAS 无锁写入不加锁有哈希冲突synchronized锁住链表头洁点 / 红黑树根节点。最大并发量等于数组长度数组长度默认为16如果链表长度 8并且数组容量 64容量小于64数组扩容链表转为红黑树节点数 6红黑树退化为链表查询复杂度由 O (n) 降到 O (logn)。二、源码剖析1 禁用null值2 初始化CAS 抢锁 (initTable)3 插入数据1无锁插入 (putVal)2synchronized锁插入4 多线程协助扩容1任务分配多个线程用 CAS 争抢全局变量transferIndex从数组尾部往前认领一段连续的数组下标。 CAS 保证同一段下标区间只会被一个线程领取不会重复干活。2头结点加锁synchronized (f) 锁住该数组下标头节点哈希表不同下标位置可以同时进行操作并发高。3链表拆分哈希表旧数组长度n是 2 的幂扩容也是2倍扩容hashn 只有两种结果hash n 0放到新数组 i位置不变低位链表 lnhash n ! 0放到新数组 in高位链表 hn4收尾所有参与扩容的线程都干完活后进入finishing阶段。完整扫一遍旧数组确认全部下标都标记了 ForwardingNode替换 table 引用为nextTab扩容生效后重置SIZECTL为新的扩容阈值。5 获取数据get()三、总结1、get()方法全程无锁依靠 volatile 保证可见性读的效率很高只有写 put / 扩容才会用到 synchronizedCAS。2、get()会读到脏数据volatile 保证可见性能读到已经完成写入的最新节点但并发场景下get 和 put 同时执行仍然存在读到旧值的并发问题读和写并发不保证原子性3、HashMap的key、value可以 nullConcurrentHashMap的key、value都不允许nullget (key) 返回 null无法区分是key不存在还是存入的value本身就是 null。4、ConcurrentHashMap适合
