Concurrent HashMap 분석:붉 은 검 은 나무의 에이전트 클래스(TreeBin)
14192 단어 ConcurrentHashMap검 붉 은 나무에이전트 클래스
1.TreeBin 내부 유형 분석
4.567914.붉 은 검 은 나무의 대리 입 니 다.붉 은 검 은 나무 에 대해 잘 모 르 는 것 은 참고 할 수 있 습 니 다.
static final class TreeBin<K,V> extends Node<K,V> {
//
TreeNode<K,V> root;
//
volatile TreeNode<K,V> first;
// （ lockState ）
volatile Thread waiter;
/**
* ：
* 1. ， ， TreeBin 。
* 2. ， TreeBin 。 lockStat + 4
* 3. （ ）， TreeBin ， ， lockState 2 0b 10 ： ， WAITER = 2;
*/
volatile int lockState;
// values for lockState（lockstate ）
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock （ ）
static final int READER = 4; // increment value for setting read lock
/**
* TreeBin ：
*/
TreeBin(TreeNode<K,V> b) {
// hash -2 TreeBin
super(TREEBIN, null, null, null);
// first treeNode
this.first = b;
// r
TreeNode<K,V> r = null;
// x
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
// null
x.left = x.right = null;
// ----------------------------------------------------------------------
// CASE1：
// ： ，
// ，r null
if (r == null) {
// null
x.parent = null;
//
x.red = false;
// r x 。
r = x;
}
// ----------------------------------------------------------------------
// CASE2：r != null
else {
// ， else ，
// k key
K k = x.key;
// h hash
int h = x.hash;
// kc key class
Class<?> kc = null;
// p
TreeNode<K,V> p = r;
// for ，
for (;;) {
// dir (-1, 1)
// -1 hash p hash
// 1 hash p hash
// ph p hash
int dir, ph;
// key
K pk = p.key;
// hash
if ((ph = p.hash) > h)
//
dir = -1;
// hash
else if (ph < h)
//
dir = 1;
// CASE3， hash hash ， case3 。
// dir 0，（-1， 1）
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// xp
TreeNode<K,V> xp = p;
// ： p
// ： p ， p p ， 。
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//
x.parent = xp;
// P ， P
if (dir <= 0)
xp.left = x;
// P ， P
else
xp.right = x;
// ， ，
r = balanceInsertion(r, x);
break;
}
}
}
}
// r TreeBin root 。
this.root = r;
assert checkInvariants(root);
}
/**
* Acquires write lock for tree restructuring.
* ： CAS LOCKSTATE ， 0， WRITER（1， ）
*/
private final void lockRoot() {
// ： lockState 0， treeBin 。
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
//
contendedLock(); // offload to separate method
}
/**
* Releases write lock for tree restructuring.
*
*/
private final void unlockRoot() {
// lockstate 0
lockState = 0;
}
/**
* Possibly blocks awaiting root lock.
*/
private final void contendedLock() {
boolean waiting = false;
// lock
int s;
for (;;) {
// ~WAITER = 11111....01
// ： TreeBin
// ：
if (((s = lockState) & ~WAITER) == 0) {
// ：
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
// TreeBin waiter null
waiter = null;
return;
}
}
// lock & 0000...10 = 0, ： lock waiter 0， 1 ， 。
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
// ： CASE2 treeBin.waiter ， lockState 1
// ， 。。
else if (waiting)
LockSupport.park(this);
}
}
/**
* Finds or adds a node.
* @return null if added
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// xp x
// x
// f
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
// ：
if (f != null)
// 。
f.prev = x;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
if (!xp.red)
x.red = true;
else {
// ， “ ”
lockRoot();
try {
// ， 。
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
}
4
TreeBin트 리 빈 의 멤버 방법,링크 를 빨 간 검 은 나무 로 바 꾸 는 방법:
/**
*
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
// b：
// n: tab
// sc: sizeCtl
Node<K,V> b; int n, sc;
if (tab != null) {
// ---------------------------------------------------------------------------
// CASE1:
// ： table 64， ， 。
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// table
tryPresize(n << 1);
// ---------------------------------------------------------------------------
// CASE2:
// ： ， node 。
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// b
synchronized (b) {
// ： ，b
if (tabAt(tab, index) == b) {
// for ， ， ~
// hd ，tl
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// node TreeBin
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
4.567914.트 리 빈 에서 찾 는 방법.
final Node<K,V> find(int h, Object k) {
if (k != null) {
// e ： first
for (Node<K,V> e = first; e != null; ) {
// s lock
// ek key
int s; K ek;
// ----------------------------------------------------------------------
// CASE1：
// (WAITER|WRITER) => 0010 | 0001 => 0011
// lockState & 0011 != 0 ： TreeBin
if (((s = lockState) & (WAITER|WRITER)) != 0) {
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
// ----------------------------------------------------------------------
// CASE2：
// ： TreeBin
// ：
else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K,V> r, p;
try {
//
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
// w
Thread w;
// U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
// 1. ， lockstate - 4
// (READER|WAITER) = 0110 => ， “ ”
// TreeBin 。
// 2.(w = waiter) != null 。
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
// unpark 。
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
지금까지 Concurrent HashMap 의 소스 분석 은 일 단락 되 었 습 니 다.더 강해 지 길 바 랍 니 다~저희 의 다른 내용 에 도 많은 관심 을 가 져 주 셨 으 면 좋 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ConcurrentHashMap 분석:예열(내부 작은 방법 분석)다음은 HashMap 멤버 들 의 방법 을 정식 적 으로 분석 하기 전에 내부 클래스 의 글자 방법 함 수 를 분석 합 니 다. 먼저 Concurrent HashMap 내부 클래스 Node 의 hash 멤버 속성 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
