ConcurrentHashMap put流程图(包含扩容逻辑(左下),counterCells计算逻辑等)
2020-10-13 16:27:42 0 举报
ConcurrentHashMap put流程图(包含扩容逻辑(左下),counterCells计算逻辑等)
作者其他创作
大纲/内容
judge if able to help transfer
addCountcalculate total node count
new a node fwd with hash = MOVED(-1)
yes
set node to the tableset node at the hash index by cas operation
do help transfer
if b style=\
init counterCells with length(2)
set fwd at this index
key or value is null
set success
get hash by spread function
ifcounterCells is null
initTableconcurrently
no
throw exception
if the hash of the node at this index is MOVED(-1)
over
ifsizeCtl < 0
ifresizeStamp changed
if binCount >= TREEIFY_THRESHOLD(8)
counterCells double its size
reloop
update b style=\
ifkey of node is the same
stride = MIN_TRANSFER_STRIDE
change the chain to red-black tree
update TRANSFERINDEX by cas
if table is null
loop itselfto guarantee data safe in concurrent scene
reset nextIndex
set node
not null
if the condition above is true
sum count and set to s
this thread yield its time slice
initailize ForwardingNode fwd with nextTab
start before loop
loop if(s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY)
set sizeCtl as capacity * 0.75(sizeCtl = c - c >>> 2)
ConcurrentHashMapthe process of transfer(do help transfer)
cas success
calculate with counterCells to save total count concurrently
set node to index by cas
check and change node chain to red-black tree
add node at tail of the last node of this position in the tablefont color=\"#000000\
is able to
cas success
if table has been transferred
changed
ifloop to the bound
not
calculate stride
help transferfont color=\"#000000\
cas occupy the privilege to transfer
spread function implement below
initTabletable initialize concurrently
success
helpTransfer
not busy or cas success
release thread occupy from sizeCtl(update sizeCtl - 1 by cas)
update sizeCtl from 0 to -1 by cas
cas occupy the privilege to operate counterCells value
retry to update baseCount by cas
loop util table has already been initialized by one thread
node chain operation
binCount ++
ConcurrentHashMapthe process of put into chm
randomly get a cell by h and set value(1)
end helptransfer(reloop to wait for table initialization)
stride = (NCPU > 1) ? (n >>> 3) / NCPU : n(n = table.length; calculate with cpu count)
calculate table index by l(ength & hash)
double check if node not change
ifnode is null
ifoneb style=\
double check if table is null
baseCount + 1 by cas
check table[index] if null
lock the current node
new a node[] array with double length
ifcurrent node is null
if the node.nextTable is null
return (key.hashCode ^ (key.hashCode >>> 16)) & Integer.MAX_VALUE
override the value to this node
initailize nextTab
if nextTab is null
lock the first node in the table
cas occupy the privilege to operate counterCells value(update cellsBusy from 0 -> 1 by cas)
iftable is null
if counterCells is also null or cas failed
set advance = true
check if node == table[index]
set node[] to table
ifbinCount>= 0
null
update sizeCtl + 1 by cas
data copy
loop if node set successget the head node at first time
get the next node in the chain
red-black tree operation
new a node[] array with length(capacity)
judge if the current thread has the condition to helptransfer by ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0)
set resizeStamp to rs
set original table length to transferIndex
update cell's value to (value + 1) by cas
recheck all the nodes in original table
table init successthen reloop
set resizeStamp to rs
recheck counterCells if null or retry to update baseCount by cas
sum total count by font color=\"#ff0000\
get random h by ThreadLocalRandom.getProbe()
end set node
loop util the transfer operation finished
new a node with key-value and set in the chain
ifcurrent node is occuppied with fwd
loop if (node.nextTab == nextTable && table == tab && (sc = sizeCtl) < 0)
set global varnextTable = nulltable = transferred tablesizeCtl = (n << 1) - (n >>> 1) [newTable length * 0.75]
declare var advance = truefinishing = false
if customizecapacity
use default capacity(16)
setbinCount = 1(node count in this chain)
loop splite the tab by stride
add and save count
ifbinCount<= 1
if the node instance of ForwardingNode
break the loop
ifsizeCtl< 0
ifnode.hash >= 0
0 条评论
下一页