ConcurrentHashMap精简篇（无源码）-一一网

【摘要】目录
Concurrent HashMap(数组+链表+红黑树)
ConcurrentHashMap.transfer()多线程扩容
ConcurrentHashMap扩容源码分析总结：
ConcurrentHashMap.put()过程总结（（hash值）& （数组长度-1）确定位置）
ConcurrentHashMap.get()（hash值）& （数组长度-1…

Concurrent HashMap(数组+链表+红黑树)

ConcurrentHashMap.transfer()多线程扩容

ConcurrentHashMap扩容源码分析总结：

ConcurrentHashMap.put()过程总结（（hash值）& （数组长度-1）确定位置）

ConcurrentHashMap.get()（hash值）& （数组长度-1）确定位置）扩容时可以get】

ConcurrentHashMap.size()

Jdk1.7ConcurrentHashMap(分段上锁)

JDK1.7和JDK1.8ConcurrentHashMap区别：

Concurrent HashMap(数组+链表+红黑树)

ConcurrentHashMap不允许key或value为null值。

重要的属性sizeCtl

-1代表正在初始化
-N 表示有N-1个线程正在进行扩容操作
0代表hash表还没有被初始化
>0 代表扩容阈值，它的值始终是当前ConcurrentHashMap容量的0.75倍

数组table中节点类型和Hash值关系（区分节点的类型就是用Hash值区分的）：

Node—-》Hash值>=0
ForwardingNod—–》用Hash值=MOVED=-1标记
TreeBin ——》用Hash值=TREEBIN=-2,TreeBin里是TreeNode集合，是红黑树结构
ReservationNode:数组中占位临时节点—-》Hash值=RESERVED=-3

ForwardingNode的情况（表示扩容时处理完毕的节点）

扩容时，老数组某个位置没有元素，则标记为ForwardingNode节点（此时无需处理所以直接标记处理完毕）
扩容时，已迁移完毕，则标记为ForwardingNode节点

初始化方法

初始化方法主要应用了关键属性sizeCtl 如果这个值〈0，表示其他线程正在进行初始化，就放弃这个操作。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。

初始化：默认初始化容量为16，加载因子为0.75的数组。将sizeCtl的值改为0.75*n作为触发扩容的阈值

ConcurrentHashMap.transfer()多线程扩容

基本认识：

每个线程扩容时，根据cpu数量确定要扩容的步长，cpu数量越多，那每个线程需要处理的步长越小，最小步长为16

假设原数组长度为64：

扩容时transferIndex记录了下一个线程需要处理的最大边界，

每当来一个线程来帮助扩容时，范围计算公式：[transferIndex-计算出的步长,transferIndex)

transferIndex的初始值=数组长度=n

第一个参与扩容的线程,[64-步长,64)=[48,64)

第二个参与扩容的线程,[48-步长,48)=[32,48)

ConcurrentHashMap扩容源码分析总结：

并发扩容总结

单线程新建nextTable，新容量一般为原table容量的两倍。
每个线程想put/remove元素时，如果访问的桶是ForwardingNode节点，则表明当前正处于扩容状态，协助一起扩容完成后再完成相应的数据更改操作。
迁移任务分配：扩容时将原table的所有桶倒序分配，每个线程每次最小分配16个桶，单个桶内元素的迁移是加锁的，但桶范围处理分配可以多线程，在没有迁移完成所有桶之前每个线程需要重复获取迁移桶范围，直至所有桶迁移完成（最后一次分的范围是【0,0)代表完毕）。
迁移元素过程：如果中间发现某个位置元素是null，则直接将ForwardingNode赋值进去，如果节点不是null：对节点上锁进行迁移，最后标记为ForwardingNode代表迁移完毕
迁移sizeCtl标记的变化：迁移过程中sizeCtl用于记录参与扩容线程的数量，增加一个扩容线程，sizeCtl+1，最后执行扩容完毕后，退出一个扩容线程sizeCtl-1,直到sizeCtl恢复到初始扩容时标记的一个复数值，代表是最后一个要退出的线程，全部迁移完成后sizeCtl更新为新table容量的0.75倍。

如果节点不是null：对节点上锁进行迁移过程。

节点的的hash值>=0代表是Node节点。则遍历Node节点为头的列表，

(node.hash)&(老数组长度)=0,则迁移到新数组中相同位置i（代表高位是0,迁移后位置不变）

(node.hash)&(老数组长度)!=0,则迁移到新数组中i+n的位置（代表高位是1,迁移后位置=原位置+原数组个数）

ConcurrentHashMap.put()过程总结（（hash值）& （数组长度-1）确定位置）

目标位置没有元素：

如果该位置没有元素，则直接赋值

目标位置有元素（此时需要判断节点类型）：

如果是ForwardingNode节点, 则代表数组正在扩容，此时需要帮助扩容
不是ForwardingNode，则对此节点加锁synchronize然后添加节点

如果hash值>0,代表此处是普通node节点，遍历链表key相等则覆盖value，如果没有找到相等的key，则链到链表最后，如果链表节点个数达到8个则变成红黑树
如果hash值=TREEBIN,则代用TreeBin的put方法，往树里添加节点
最后添加完后需要判断是否需要扩容，需要扩容的扩容，元素总个数baseCount+1

ConcurrentHashMap.get()（hash值）& （数组长度-1）确定位置）扩容时可以get】

不同的节点类型查找不一样，

如果是ForwardingNode,则调用ForwardingNode.find(),此时是从ForwardingNode的nextTable里进行查询节点，返回key相等的元素
如果目标位置是TreeBin,则调用TreeBin的find，遍历红黑树，返回key相等的元素
如果是Node，则遍历node链，返回key相等的元素

ConcurrentHashMap.size()

1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount。因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell(是baseCount++失败后放到CounterCell里)数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数。

方法是否加锁：

[CAS]ConcurrentHashMap的get方法不加锁，get方法采用了unsafe.tabAt()方法，来保证线程安全。

[Synchronized]ConcurrentHashMap的put(),remove(),迁移都需要加锁CAS+Synchronized。

ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

ConcurrentHashMap弱一致性，hashmap强一直性。

ConcurrentHashMap可以支持在迭代过程中，向map添加新元素，而HashMap则抛出了ConcurrentModificationException