ConcurrentHashMapソース読解02
25012 ワード
ConcurrentHashMapソース読解02
前言
前編では,ConcurrentHashMapの定数,メモリセルおよびメンバ変数について述べた.今日は,テストケースと結びつけて,ConcurrentHashMapにおけるput法の実現原理を探究する.
本文
テストケースの作成
次のようなテストケースを作成します. @Test
public void test(){
Map map = new ConcurrentHashMap();
map.put("a",1);
}
ConcurrentHashMap内のノード配列を初期化する際にU.compareAndSwapIntメソッドが使用されることが分かったので、まずUを見てみましょう.
UnSafe mechanics
// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final long ABASE;
private static final int ASHIFT;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class> k = ConcurrentHashMap.class;
SIZECTL = U.objectFieldOffset
(k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy"));
Class> ck = CounterCell.class;
CELLVALUE = U.objectFieldOffset
(ck.getDeclaredField("value"));
Class> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak);
int scale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw new Error(e);
}
}
この静的コードブロックは上の初期化されていない変数を初期化した:U,UnSafeの唯一のインスタンスを取得する方法によって初期化した
U.objectFieldOffsetメソッドは、ConcurrentHashMapクラスのメモリにおける対応するフィールドのクラスヘッダアドレスに対するオフセット量を取得します.
SIZECTRLは、ConcurrentHashMapクラスのsizeCtlフィールドに対応する.TRANSFERINDEX、transferIndexフィールドに対応する.BASECOUNT、baseCountフィールドに対応する.CELLSBUSY、cellsBusyフィールドに対応する.CELLVALUE、CounterCellクラスのvalueフィールドに対応する.
U.arrayBaseOffsetメソッドでは、配列の最初の要素のオフセットアドレスを取得できます.
ABASEは、Node[]を要素とする配列の最初の要素のオフセットアドレスを取得する.
U.arrayIndexScale法は配列の変換因子,すなわち配列中の要素の増分アドレスを取得することができる.arrayBaseOffsetをarrayIndexScaleと組み合わせて使用すると、配列内の各要素のメモリ内の位置を特定できます.
scaleは、Node[]を要素とする配列の変換係数を取得します.
Integer.numberOfLeadingZeros法の役割は、符号ビットを含む符号なし整数iの最高非ゼロビットの前の0の個数を返すことである.iが負の場合、この方法は0を返し、シンボルビットは1である.例えば、10のバイナリ表現が0000 0000 0000 0000 0000 0000 0000 1010 javaの整数長は32ビットである.では、この方法は28を返します.
ASHIFT,31はscaleの最高非ゼロビット前の0の個数を減算した結果である.
デバッグ分析
putメソッドへのアクセス: /**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
このtableでは、指定したkeyが指定したvalueに対応します.キーもvalueもnullではいけません.元のkeyと同じkeyをパラメータとしてgetメソッドを呼び出すことで対応するvalueを取得できる.
次にputValメソッドに入ります. /** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
(1)hash値の算出
まず,keyまたはvalueが空であれば空ポインタ異常を投げ出す判定を行った. if (key == null || value == null) throw new NullPointerException();
次にspreadメソッドを呼び出してhash値を計算します. int hash = spread(key.hashCode());
spreadの方法を見てみましょう. /**
* Spreads (XORs) higher bits of hash to lower and also forces top
* bit to 0. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
(XORs)より高いハッシュ値をより低いハッシュ値に拡張し、最上位を0に強制します.このテーブルは2のべき乗マスクを使用しているため、現在のマスクの上でビット単位で変化するハッシュセットだけが常に競合します.(既知の例には、連続整数を小さなテーブルに保存する浮動小数点キーセットが含まれる.)そこで,より高いレベルの影響を下に伝播する変換を適用した.ビット拡張の速度、実用性、品質の間にはバランスがあります.多くの一般的なハッシュ・セットが合理的に分布しているため(拡張から利益を得ることはできません)、ツリーを使用して大量のハッシュ・セットを処理します.
ここでhash値計算方法ではビット演算を用いた.
putValメソッドに戻って下を見続けます. int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
(2)チェーンテーブル配列初期化
binCount変数を定義し、forループに入り、チェーンテーブル配列を巡回する:まず空を判定し、tabがnullまたは配列長が0の場合、チェーンテーブル配列を初期化する: if (tab == null || (n = tab.length) == 0)
tab = initTable();
チェーンテーブル配列を初期化する方法initTableに入ります. /**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
sizeCtlサイズでレコードを使用してテーブルを初期化します.
1、チェーンテーブル配列tabとint変数scが定義され、いずれも初期化されていない.2、whileサイクルに入り、現在のtableが空か長さが0かどうかを判断する.2.1.sizeCtlが0より小さいかどうかを判断し、成功したと判断するとThreadを呼び出す.yield();現在のスレッドをRUNNING状態からREADY状態に移行します.
テストケースの作成
次のようなテストケースを作成します.
@Test
public void test(){
Map map = new ConcurrentHashMap();
map.put("a",1);
}
ConcurrentHashMap内のノード配列を初期化する際にU.compareAndSwapIntメソッドが使用されることが分かったので、まずUを見てみましょう.
UnSafe mechanics
// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long SIZECTL;
private static final long TRANSFERINDEX;
private static final long BASECOUNT;
private static final long CELLSBUSY;
private static final long CELLVALUE;
private static final long ABASE;
private static final int ASHIFT;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class> k = ConcurrentHashMap.class;
SIZECTL = U.objectFieldOffset
(k.getDeclaredField("sizeCtl"));
TRANSFERINDEX = U.objectFieldOffset
(k.getDeclaredField("transferIndex"));
BASECOUNT = U.objectFieldOffset
(k.getDeclaredField("baseCount"));
CELLSBUSY = U.objectFieldOffset
(k.getDeclaredField("cellsBusy"));
Class> ck = CounterCell.class;
CELLVALUE = U.objectFieldOffset
(ck.getDeclaredField("value"));
Class> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak);
int scale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw new Error(e);
}
}
この静的コードブロックは上の初期化されていない変数を初期化した:U,UnSafeの唯一のインスタンスを取得する方法によって初期化した
U.objectFieldOffsetメソッドは、ConcurrentHashMapクラスのメモリにおける対応するフィールドのクラスヘッダアドレスに対するオフセット量を取得します.
SIZECTRLは、ConcurrentHashMapクラスのsizeCtlフィールドに対応する.TRANSFERINDEX、transferIndexフィールドに対応する.BASECOUNT、baseCountフィールドに対応する.CELLSBUSY、cellsBusyフィールドに対応する.CELLVALUE、CounterCellクラスのvalueフィールドに対応する.
U.arrayBaseOffsetメソッドでは、配列の最初の要素のオフセットアドレスを取得できます.
ABASEは、Node[]を要素とする配列の最初の要素のオフセットアドレスを取得する.
U.arrayIndexScale法は配列の変換因子,すなわち配列中の要素の増分アドレスを取得することができる.arrayBaseOffsetをarrayIndexScaleと組み合わせて使用すると、配列内の各要素のメモリ内の位置を特定できます.
scaleは、Node[]を要素とする配列の変換係数を取得します.
Integer.numberOfLeadingZeros法の役割は、符号ビットを含む符号なし整数iの最高非ゼロビットの前の0の個数を返すことである.iが負の場合、この方法は0を返し、シンボルビットは1である.例えば、10のバイナリ表現が0000 0000 0000 0000 0000 0000 0000 1010 javaの整数長は32ビットである.では、この方法は28を返します.
ASHIFT,31はscaleの最高非ゼロビット前の0の個数を減算した結果である.
デバッグ分析
putメソッドへのアクセス:
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
このtableでは、指定したkeyが指定したvalueに対応します.キーもvalueもnullではいけません.元のkeyと同じkeyをパラメータとしてgetメソッドを呼び出すことで対応するvalueを取得できる.
次にputValメソッドに入ります.
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
(1)hash値の算出
まず,keyまたはvalueが空であれば空ポインタ異常を投げ出す判定を行った.
if (key == null || value == null) throw new NullPointerException();
次にspreadメソッドを呼び出してhash値を計算します.
int hash = spread(key.hashCode());
spreadの方法を見てみましょう.
/**
* Spreads (XORs) higher bits of hash to lower and also forces top
* bit to 0. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
(XORs)より高いハッシュ値をより低いハッシュ値に拡張し、最上位を0に強制します.このテーブルは2のべき乗マスクを使用しているため、現在のマスクの上でビット単位で変化するハッシュセットだけが常に競合します.(既知の例には、連続整数を小さなテーブルに保存する浮動小数点キーセットが含まれる.)そこで,より高いレベルの影響を下に伝播する変換を適用した.ビット拡張の速度、実用性、品質の間にはバランスがあります.多くの一般的なハッシュ・セットが合理的に分布しているため(拡張から利益を得ることはできません)、ツリーを使用して大量のハッシュ・セットを処理します.
ここでhash値計算方法ではビット演算を用いた.
putValメソッドに戻って下を見続けます.
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
(2)チェーンテーブル配列初期化
binCount変数を定義し、forループに入り、チェーンテーブル配列を巡回する:まず空を判定し、tabがnullまたは配列長が0の場合、チェーンテーブル配列を初期化する:
if (tab == null || (n = tab.length) == 0)
tab = initTable();
チェーンテーブル配列を初期化する方法initTableに入ります.
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
sizeCtlサイズでレコードを使用してテーブルを初期化します.
1、チェーンテーブル配列tabとint変数scが定義され、いずれも初期化されていない.2、whileサイクルに入り、現在のtableが空か長さが0かどうかを判断する.2.1.sizeCtlが0より小さいかどうかを判断し、成功したと判断するとThreadを呼び出す.yield();現在のスレッドをRUNNING状態からREADY状態に移行します.
unsafe.compareAndSwapInt(this, valueOffset, expect, update);
以上より分かるように、SIZECTLがscに等しい場合、SIZECTLを−1としてtrueを返すことに成功した.すなわち、I現在のチェーンテーブルが空であればチェーンテーブルを初期化し、n−(n>>2)の値をsc.IIに与える.scの値をsizeCtlに与える.続いてループを飛び出し、tabを返し、チェーンテーブル配列の初期化が完了する.
(3)ノード位置が空の場合の割付操作
putValメソッドに戻ります.チェーンテーブルの配列が空でない場合、(f=tabAt(tab,i=(n-1)&h)))==nullを判断します.tabAtメソッドを見てみましょう.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
U.getObjectVolatileメソッド:public native Object getObjectVolatile(Object obj,long offset);objオブジェクトのoffsetオフセットアドレスに対応するobject型fieldの値を取得し、volatile loadの意味をサポートします.パラメータ:読み出しが必要なfieldを含むオブジェクト
objにおけるobject型fieldのオフセット量従来tabAtメソッドは,hash値を用いてインデックス位置を決定する配列要素,すなわち対応するチェーンテーブル配列ノードを取得するためにメモリオフセットアドレスを用いていた.対応するインデックス位置にチェーンテーブル配列ノードが存在する場合、判定は成立し、次の判定に進む.
if (casTabAt(tab, i, null,
new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
casTabAtの方法を見てみましょう.
static final boolean casTabAt(Node[] tab, int i,
Node c, Node v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
U.compareAndSwapObjectメソッド:public native boolean compareAndSwapObject(Object obj,long offset,Object expect,Object update);objのoffset位置でobject fieldと所望の値を比較し、同じであれば更新する.この方法の動作は原子的であるべきであるため,object fieldを中断不可能に更新する方法を提供する.パラメータ:fieldを変更するオブジェクトを含む
objのobject型fieldのオフセット量fieldに存在したい値希望値expectがfieldの現在の値と同じである場合、filedの値をこの新しい値に戻す値に設定します:fieldの値が変更されるかどうか原子操作判定により,オフセットアドレスiのノードが空でないことを保証し,判定が成立すると,すなわちノードが変更されるとループから飛び出す.
(4)hash落下点にノードがありhash値が-1である場合
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
helpTransferの方法を見てみましょう.
/**
* Helps transfer if a resize is in progress.
*/
final Node[] helpTransfer(Node[] tab, Node f) {
Node[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
ForwardingNode:転送操作時にコンテナヘッダに挿入されたノード.現在のノードがForwardingNodeノードであると判断し、ヘッダノードではないと判断し、resizeStampメソッドを呼び出す.
/**
* Returns the stamp bits for resizing a table of size n.
* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
*/
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
次に、条件が満たされた場合、拡張操作を行います.
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node[] tab, Node[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode fwd = new ForwardingNode(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node ln, hn;
if (fh >= 0) {
int runBit = fh & n;
Node lastRun = f;
for (Node p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin t = (TreeBin)f;
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
デフォルトの拡張長さは、元のチェーンテーブル配列の長さの2倍です.
(5)hash落下点に既にノードがある場合
ConcurrentHashMapがどのような操作をしたかを見てみましょう.
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
onlyIfAbsentがfalseの場合、元の値を置き換えます.onlyIfAbsentがtrueの場合、変更は行われません.