ConcurrentHashMap 분석:put 방법 소스 코드 분석
20665 단어 ConcurrentHashMapput
put()방법 은 HashMap 소스 코드 분석 을 병행 하 는 중점 적 인 방법 이다.여 기 는 병발 확장,통 위치 찾기 등 과 관련된다.
// Map put
public V put(K key, V value) {
return putVal(key, value, false);
}
// Map put
// Key:
// value：
// onlyIfAbsent： ：
// false， put ， Map K,V ，
// true， put ， Map K,V ， ，
final V putVal(K key, V value, boolean onlyIfAbsent) {
// k v null
if (key == null || value == null) throw new NullPointerException();
// spread ， ， hash
int hash = spread(key.hashCode());
// binCount k-v node ，
// =0 null，node
// >0 ， ， k-v node ， binCount
// =2 ** **
int binCount = 0;
// tab map table
//
for (Node<K,V>[] tab = table;;) {
// f
// n
// i key ，
// fh hash
Node<K,V> f; int n, i, fh;
// -----------------------------------------------------------------------------
// CASE1： ， map table ...
if (tab == null || (n = tab.length) == 0)
// map table
tab = initTable();
// -----------------------------------------------------------------------------
// CASE2：table ， ， f null
// i key key table ，tabAt i f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// k-v
// casTabAt CAS Node i ， true false
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// -----------------------------------------------------------------------------
// CASE3：table ， f null， f hash fh=-1：
// ， FWD(forwarding)
// CASE3 ： FWD ， map ..
else if ((fh = f.hash) == MOVED)
// f FWD ， map ...
// ~
tab = helpTransfer(tab, f);
// -----------------------------------------------------------------------------
// CASE4：CASE1-3 ， TreeBin
else {
// ： key ， OldVal， put
V oldVal = null;
// synchronized “ ”（** “ ”**)
synchronized (f) {
// -----------------------------------------------------------------------
// CASE5：tabAt(tab, i) == f
// ： ？
// ， sync f （ ~）
if (tabAt(tab, i) == f) {// ， f ， ！
// ------------------------------------------------------------------
// CASE6：fh >= 0)
// ， , ：
// static final int MOVED = -1; FWD(forwarding)
// static final int TREEBIN = -2;
if (fh >= 0) {
// 1. key key ， ，binCount
// 2. key key ， 。binCount （binCount - 1）
binCount = 1;
// ，e 。
for (Node<K,V> e = f;; ++binCount) {
// key
K ek;
// --------------------------------------------------------
// CASE7：
// ：e.hash == hash
// ： hash hash ,
// ：((ek = e.key) == key ||(ek != null && key.equals(ek)))
// ： key ， ~
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// oldVal
oldVal = e.val;
// putVal onlyIfAbsent： ：
// false， put ， Map K,V ，
// true， put ， Map K,V ， ，
if (!onlyIfAbsent)
e.val = value;
break;
}
// --------------------------------------------------------
// CASE8：
// key ， :
// 1.
// 2. null， null， ， 。
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// ------------------------------------------------------------------
// CASE9：f instanceof TreeBin
// ， TreeBin
//（ ： ）
else if (f instanceof TreeBin) {
// p key ， putTreeVal 。
Node<K,V> p;
// binCount 2， binCount <= 1 ， 2 （ addCount ）
binCount = 2;
// ， key key ， ：
// putTreeVal ， null，
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
// oldVal
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// ------------------------------------------------------------------
// CASE10：binCount != 0
// null，
if (binCount != 0) {
// binCount>=8
if (binCount >= TREEIFY_THRESHOLD)
// 8， ：
//
treeifyBin(tab, i);
// key， k-v ， v 。
if (oldVal != null)
return oldVal;
break;
}
}
}
// Map ：
// 1. table
// 2. ， 。
addCount(1L, binCount);
return null;
}
처음 원 소 를 넣 었 을 때 통 배열 초기 화:
/**
* table
*/
private final Node<K,V>[] initTable() {
// tab: map.table
// sc: sizeCtl
// sizeCtl： 0， table 、 :
// sizeCtl<0 table :
//（1）=-1， 。（ ， ）
//（2）=-(1 + nThreads)， n 。
// sizeCtl>=0 table ：
//（3）=0， ， table ， DEFAULT_CAPACITY --> 16。
//（4）>0， sizeCtl table 。
Node<K,V>[] tab; int sc;
// ： map.table ...
while ((tab = table) == null || tab.length == 0) {
// -----------------------------------------------------------------------------
// CASE1: sizeCtl) < 0
// sizeCtl < 0 2 ：
//（1）-1， table 。
//（2）-(1 + nThreads)， n 。
if ((sc = sizeCtl) < 0)
// sizeCtl -1， table ， table ， ...
Thread.yield();
// -----------------------------------------------------------------------------
// CASE2：sizeCtl) >= 0 U.compareAndSwapInt(this, SIZECTL, sc, -1) true
// U.compareAndSwapInt(this, SIZECTL, sc, -1)： CAS sizeCtl -1，
// sizeCtl -1， true， false。
// true ， else if ， sizeCtl=-1 ， else if ， ~
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// ----------------------------------------------------------------------
// CASE3: ？
// table ， .. 。
// ， if ， table 。
if ((tab = table) == null || tab.length == 0) {
// sc 0 ：
//（3）=0， ， table ， DEFAULT_CAPACITY --> 16。
//（4）>0， sizeCtl table 。
// sc 0, table sc table ，
// 16 DEFAULT_CAPACITY
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// nt
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// nt table、tab
table = tab = nt;
// sc ：0.75n
sc = n - (n >>> 2);
}
} finally {
// sc sizeCtl， 2 ：
// 1、 CASE2 ， CASE3 ：
// ， map.table ， ，sc 。
// 2、 CASE2 ， CASE3 ：
// ， map.table ， CASE2 ，
// sizeCtl -1 ， ， sc CASE2 sc 。
sizeCtl = sc;
}
break;
}
}
return tab;
}
(2)sizeCtl 은 초기 화 후 확장 문턱 을 저장 합 니 다.
(3)확장 문턱 은 통 배열 의 크기 의 0.75 배,통 배열 의 크기 는 map 의 용량,즉 최대 몇 개의 요 소 를 저장 하 는 지 쓰 여 있다.
3.addCount 방법(난점)
addCount방법의 원본 코드 를 읽 기 전에LongAdder원본 코드 를 다시 익히 는 것 이 좋다.당신 을 데 리 고 입문 LongAdder 소스 코드 를 해석 합 니 다.addCount방법 작용:매번 원 소 를 첨가 한 후 원소 의 수량 을 1 로 늘 리 고 확장 문턱 에 도 달 했 는 지 판단 하 며 도달 하면 확장 또는 확장 을 협조 한다.
/**
* Map ：
* 1. table
* 2. ，
*/
private final void addCount(long x, int check) {
// as LongAdder.cells
// b LongAdder.base
// s map.table
CounterCell[] as; long b, s;
// ------------------------- table ----------------------------------
// CASE1:
// (as = counterCells) != null
// ：true-> cells ， hash cell
// false-> base（ ）
// !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)
// ：false-> base ， base ， ， cells
// true-> base ， base ， cells。
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// if ？
// true-> cells ， hash cell
// true-> base ， base ， cells。
// a hash cell
CounterCell a;
// v cell
long v;
// m cells
int m;
// true -> false->
boolean uncontended = true;
// ---------------------------------------------------------------------------
// CASE2:
// ：as == null || (m = as.length - 1) < 0
// true-> base （CASE1 ）， if ， fullAddCount ..
// （fullAddCount LongAdder.longAccumulate ）
// ：a = as[ThreadLocalRandom.getProbe() & m]) == null ：cells
// true-> cell ， fullAddCount cell， .
// ：!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
// ： cell ~
// false-> false， cas cell
// true-> true, cas cell ， fullAddCount cells。
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
) {
fullAddCount(x, uncontended);
// fullAddCount ， ， 。
return;
}
if (check <= 1)
return;
// sumCount sum = base + cells[0] + ... + cells[n]，
s = sumCount();
}
// ------------------------- ， ----------------------------
// CASE3:
// check >= 0 put addCount，check < 0 remove addCount
if (check >= 0) {
// tab map.table
// nt map.nextTable
// n map.table
// sc sizeCtl
Node<K,V>[] tab, nt; int n, sc;
/**
* sizeCtl < 0
* 1. -1 table （ table ）， ..
* 2. table , 16 ： 16 ：（1 + nThread）
*
* sizeCtl = 0， table DEFAULT_CAPACITY
*
* sizeCtl > 0
*
* 1. table ，
* 2. table ， （ ）
*/
// ~
// ：s >= (long)(sc = sizeCtl)
// true -> 1. sizeCtl ..
// 2. sizeCtl ， ， s （ ）
// false -> table （ ）
// ：(tab = table) != null true
// ：(n = tab.length) < MAXIMUM_CAPACITY
// true -> table ， 。
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
//
// eg: 16 -> 32 ：1000 0000 0001 1011
// ？
// ， map 16 32 ， 1000 0000 0001 1011
int rs = resizeStamp(n);
// --------------------------------------------------------------------------
// CASE4:
// ： table ， ， table
if (sc < 0) {
// --------------------------------------------------------------
// CASE2: 1~4 true ， ~
// ：(sc >>> RESIZE_STAMP_SHIFT) != rs
// true ->
// false ->
// ：JDK1.8 bug,jira , sc == (rs << 16 ) + 1
// true -> ，
// false -> ，
// ：JDK1.8 bug,jira , :
// sc == (rs << 16) + MAX_RESIZERS
// true-> 65535 - 1
// false->
// ：(nt = nextTable) == null
// true ->
// false ->
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
// 1~4 true ， ~
break;
// --------------------------------------------------------------
// CASE5:
// ： table （ ，CASE4 ） 。
// ： ， sc 16 1， ~
// ：
// 1. sizeCtl，
// sc ，CAS 。( ~)
// 2.transfer sizeCtl。
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// （ ）： ， nextTable ， ~
transfer(tab, nt);
}
// --------------------------------------------------------------------------
// CASE6: CAS sc， true， false
// ， ** ** ， transfer :
// rs << RESIZE_STAMP_SHIFT： 16 eg:
// 1000 0000 0001 1011 << 16 1000 0000 0001 1011 0000 0000 0000 0000
// (rs << RESIZE_STAMP_SHIFT) + 2) ：
// 1000 0000 0001 1011 0000 0000 0000 0000 + 2
// => 1000 0000 0001 1011 0000 0000 0000 0010， :
// sizeCtl 16 : 1000 0000 0001 1011
// sizeCtl 16 : 0000 0000 0000 0010 (1 + nThread)， ， ~
// n ？
// eg: (rs << RESIZE_STAMP_SHIFT) + 2 2， 1 + 1， 1 1*Thread， (1+1*Threads)
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// （ ）： nextTable
transfer(tab, null);
// table
s = sumCount();
}
}
}
(1)요소 개수 의 저장 방식 은 LongAdder 류 와 유사 하 며 서로 다른 세그먼트 에 저장 되 어 서로 다른 스 레 드 가 동시에 size 를 업데이트 할 때의 충돌 을 감소 합 니 다.
(2)원소 개 수 를 계산 할 때 이 단락 의 값 과 baseCount 를 더 해서 총 원소 개 수 를 계산한다.
(3)정상 적 인 상황 에서 sizeCtl 은 확장 문턱 을 저장 하고 확장 문턱 은 용량 의 0.75 배 이다.
(4)용량 확장 시 sizeCtl 고위 저장 용량 확장 소인(resizeStamp),하위 저장 용량 확장 라인 수 1(1+nThreads)추가;
(5)다른 스 레 드 에 요 소 를 추가 한 후에 확장 이 존재 하 는 것 을 발견 하면 확장 행렬 에 도 가입 할 것 이다.
이상 은 바로 Concurrent HashMap 소스 코드 의 put 데 이 터 를 저장 하 는 방법 과 관련 방법 입 니 다.transfer 이전 데이터이 방법 이 복잡 하기 때문에 다음 글 에서 따로 분석 하 겠 습 니 다.저희 의 다른 내용 에 도 많은 관심 을 가 져 주 셨 으 면 좋 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ConcurrentHashMap 분석:예열(내부 작은 방법 분석)다음은 HashMap 멤버 들 의 방법 을 정식 적 으로 분석 하기 전에 내부 클래스 의 글자 방법 함 수 를 분석 합 니 다. 먼저 Concurrent HashMap 내부 클래스 Node 의 hash 멤버 속성 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
