ConcurrentHashmap

目录

ConcurrentHashmap

jdk1.7

底层原理

分段锁机制

扩容机制

jdk1.8之后

put流程

读操作

扩容机制

• jdk1.7

  • 底层原理

    • jdk1.7之前，底层是维护一个segment数组，每一个数组元素是一个segment分段锁加数组加链表的数据结构，每个segment既是分段锁，也是一个小的独立的hashmap

    • 哈希定位：会经过两次哈希定位，第一次是为了找到key所属segment下标，第二次是找到segment中对应的数组下标

    • 分段锁机制

      • 写操作：只会锁住对应的segment，不会影响其他的segment，最大并发量=segment数组长度

      • 读操作：读操作不会加锁，主要依靠segment中的数组的volatile关键字，保障可见性

      • 锁升级：如果segment竞争激烈，reentrantlock会将自旋锁升级为重量级锁

    • 扩容机制

      • 只扩容对应的segment中的数组，对其他的没有影响，同时也只会锁住对应的segment

• jdk1.8之后

  • 底层数据结构编程数组+链表/红黑树，forwardingnode是代表当前桶正在进行扩容机制

  • put流程

    • 首先计算key的哈希值，找到对应的数组下标；然后，判断当前桶是否为空，如果是空的用cas操作尝试插入节点，如果失败会进行自旋重试；不为空，需要检查是否为forwardingnode，如果是需要协助扩容；不是，对头节点加synchronized锁，如果当前桶是链表结构，先遍历查找key，如果存在就更新value值，不存在就插入到尾节点，如果是红黑树，就执行红黑树对应的更新/插入方法；然后，需要判断当前链表长度是否大于等于8，如果是需要转换成红黑树；最后检查当前数组容量是否超过阈值，超过需要进行扩容机制。

  • 读操作

    • 全程不加锁，主要依靠volatile保证可见性

    • 计算哈希值定位到对应桶，如果头节点就是目标key，直接返回value；如果不是就继续向下遍历链表/红黑树，找到对应key，返回value，通过volatile保证最新值

  • 扩容机制

    • 创建一个新的数组，给原数组的每个桶加锁，将节点迁移到新数组中去；如果有其他线程操作到这些桶，会检测到forwardingnide，这些线程就会主动协作扩容，扩容完成之后将table引用指向新数组