자바 집합 - ConcurrentHashMap 소스 코드 개요 (JDK 1.8 기반)
21623 단어 자바 집합
개술
2. 소스 코드 설명
1, 구조 함수
1.1 인삼 없 는 구조 함수
1.2 지 정 된 용량, 로드 인자, 병렬 단계 의 구조 함수
2, put 방법
2.1 initTable () Node 배열 을 초기 화 하 는 방법
2.2 addCount(long x, int check) node 의 데 이 터 를 통계 하여 확장 이 필요 하 다 면 확장 합 니 다.
3, get 방법
4, size 방법
5, remove 방법
대비
1. 병발 단계
2, 데이터 구조
3. 링크 의 삽입
4, 확장
개술
jdk 1.8 의 Concurrent HashMap 은 세그먼트 잠 금 개념 을 취소 했다. 구조 함수 에서 병발 등급 이라는 매개 변 수 를 지정 할 수 있 지만 실제 적 으로 초기 용량 이 병발 등급 보다 작 으 면 초기 용량 의 값 을 병발 등급 의 값 으로 설정 한 다음 에 병발 등급 이라는 매개 변 수 를 사용 하지 않 는 다 고 판단 했다.1.8 에서 자 물 쇠 는 더욱 세분 화 되 었 기 때문에 Node 배열 의 모든 아래 표 시 된 헤드 노드 요 소 를 사용 하여 자 물 쇠 를 추가 합 니 다.용량 이 있 는 만큼 자 물 쇠 를 잠 그 는 것 과 같다.또한 확장 을 진행 할 때 일부 데이터 의 접근 이 막 히 지 않도록 지원 한다.
2. 소스 코드 설명
1, 구조 함수
1.1 인삼 없 는 구조 함수
public ConcurrentHashMap() {
}기본 구조 함 수 를 사용한다 면 초기 용량 은 기본적으로 16 이다.
1.2 지 정 된 용량, 로드 인자, 병렬 단계 의 구조 함수
이 세 개의 매개 변수의 구조 함수 외 에 또 다른 두 개의 구조 함수 가 있 는데 그것 이 바로:
ConcurrentHashMap (int initialCapacity): 초기 용량 을 지정 합 니 다.
ConcurrentHashMap (int initialCapacity, float loadFactor): 초기 용량 과 로드 인 자 를 지정 합 니 다.
여기 서 세 개의 매개 변수 가 있 는 구조 함수 만 설명 합 니 다.
한 곳 을 주의 하 십시오: 초기 용량 은 로드 인자 와 관련 이 있 습 니 다.
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
//
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// ，
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
// size
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
// size 2
int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size);
//
this.sizeCtl = cap;
}2, put 방법
put 방법 에서 puutVal 방법 을 호출 합 니 다.
key 와 value 는 null 일 수 없습니다. 그렇지 않 으 면 이상 을 던 집 니 다.
put 흐름:
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key value null， ， Map null
if (key == null || value == null) throw new NullPointerException();
// key hash
int hash = spread(key.hashCode());
int binCount = 0;
// Node tab ，
for (Node[] tab = table;;) {
Node f; int n, i, fh;
// tab null
if (tab == null || (n = tab.length) == 0)
// Node ，
// ，
// ， ， tab null
tab = initTable();
// (n - 1) & hash
// tabAt Node
// null， Node ， cas
// ， ，
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// f ，
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);// 。
// node ， ，
//
else {
V oldVal = null;
// synchronized ，
synchronized (f) {
// f
// ， ，
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
// key ， if
if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
//
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
//
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}//
//
if (binCount != 0) {
// 8，
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);//
// if， put
if (oldVal != null)//
return oldVal;
break;
}
}
}
// ，
// node ，
// binCount， 0，
addCount(1L, binCount);
return null;
} 2.1 initTable () Node 배열 을 초기 화 하 는 방법
CAS 원자 로 sizeCtl 의 값 을 수정 합 니 다. 성공 한 스 레 드 를 수정 해 야 초기 화 할 수 있 습 니 다. 한 스 레 드 만 수정 할 수 있 습 니 다. 다른 스 레 드 는 이 값 이 수 정 된 것 을 발견 하면 Node 배열 이 초기 화 될 때 까지 CPU 를 양보 합 니 다.
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// sizeCtl 0 cpu（ ）
// sizeCtl ， sc，sc
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// cas sizeCtl -1，
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// ， table null，
if ((tab = table) == null || tab.length == 0) {
// sc ， n， new ConcurrentHashMap ， 16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node,?>[n];// Node
table = tab = nt;// Node table
sc = n - (n >>> 2);
}
} finally {
// ， 。
sizeCtl = sc;
}
break;
}
}
return tab;
} 2.2 addCount(long x, int check) node 의 데 이 터 를 통계 하여 확장 이 필요 하 다 면 확장 합 니 다.
노드 요소 + 1 에 성공 한 후 (fullAddCount 방법 CAS 작업 으로 병발 안전 보장) 현재 노드 요소 개 수 를 계산 합 니 다.
현재 원소 의 개수 가 용량 한도 값 에 도 달 했 는 지 판단 하고 만약 그렇다면 용량 을 늘린다.
/**
* 。
* ， :-1 ， -(1 + )。
* null ， ， 0。
* ， 。
*/
private transient volatile int sizeCtl;
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// ：if
if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;//
// ThreadLocalRandom.getProbe()：
// 0
if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
// CELLVALUE CounterCell value
// +1
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// ， fullAddCount
// uncontended： false， ； true
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();//
}
//
if (check >= 0) {
Node[] tab, nt; int n, sc;
// s sizeCtl ， sizeCtl ， ，
//
// while ，
// ， ，
while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {// sc < 0
// ， while
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
break;
// ，
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// ， ， nextTab ，
else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
// See LongAdder version for explanation
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // 0
h = ThreadLocalRandom.getProbe();//
wasUncontended = true;//
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
// if
if ((as = counterCells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {// if
if (cellsBusy == 0) { // Try to attach new Cell
//
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) {
rs[j] = r;//
created = true;// true
}
} finally {
cellsBusy = 0;// 0
}
if (created)// created true，
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
// +1
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
else if (counterCells != as || n >= NCPU)
collide = false; // At max size or stale
else if (!collide)
collide = true;
// （ ）
else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {//
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;// 0（ ）
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
}
//
else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {//
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;// 0（ ）
}
if (init)
break;
}
// +1
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
} 3, get 방법
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread(key.hashCode());//
// null
if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
// key Node， node value
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
// hash 0 ， node（TreeNode） key
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//
if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
// null
return null;
} 4, size 방법
sumCount 방법 으로 계산 하기
Counter Cell 배열 을 엄 격 히 하고 여러 스 레 드 를 Counter Cell 배열 에서 통계 한 데 이 터 를 합 쳐 총 수 를 얻 습 니 다.
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
// ，
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
//
return sum;
}5, remove 방법
final V replaceNode(Object key, V value, Object cv) {
// key hash
int hash = spread(key.hashCode());
for (Node[] tab = table;;) {//
Node f; int n, i, fh;
// node ， hash ， null
if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// ， node
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
// hash
synchronized (f) {
//
if (tabAt(tab, i) == f) {
if (fh >= 0) { //
// ， ，
validated = true;
for (Node e = f, pred = null;;) {
K ek;
if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
// ， findTreeNode ，
// node 8
else if (f instanceof TreeBin) {
validated = true;
TreeBin t = (TreeBin)f;
TreeNode r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// key
if (validated) {
if (oldVal != null) {
if (value == null)
//
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
} 대비
1. 병발 단계
1.7 에서 segment 배열 을 사용 하여 병발 단계 (기본 값 16) 1.8 에서 Node 배열 의 머리 몇 시 를 잠 금 대상 으로 하고 병발 단 계 는 Node 배열 의 길이, 즉 Map 집합 용량 이다.
2, 데이터 구조
1.7 에서 만약 에 하나의 노드 아래 에 여러 개의 데이터 가 대응 하면 이 여러 데이터 의 데이터 구 조 는 링크 로 나타난다.
1.8 에서 노드 아래 에 표 시 된 데이터 가 여러 개 에 대응 하면 이 여러 데이터 의 수량 이 8 보다 많 으 면 빨간색 과 검은색 나무 이 고 8 보다 적 으 면 배열 이다.
3. 링크 의 삽입
1.7 헤드 삽입 법 사용
1.8 꼬리 삽입 법 사용
4, 확장
1.7 의 확장 은 segment 대상 중의 작은 노드 배열 을 확장 하 는 것 이다.
1.8 의 확장 은 전체 노드 그룹 을 확장 하 는 동시에 다 중 스 레 드 확장 을 지원 하 며 확장 할 때 전체 노드 그룹 을 잠 그 지 않 아 일부 데이터 의 접근 을 지원 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Spring 자동 조립 이해현재 이 클래스 는 @ Repository 표지 가 있 고 내부 에 @ Autowired 가 있 습 니 다. 이 클래스 가 구성 요소 에 스 캔 되면 spring 은 자동 으로 bean 을 생 성하 고 dbAcess...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
