ConccurrenthashMap 1.7 1.8を読みます.
9760 ワード
概要:
Conccurrenthashmapはjava併発において重要なクラスであり、HashTableの代わりに、同時進行可能なhashtalbeを実現する.私は1.7と1.8の中の実現をもって、それぞれConcerenthashMapのキーデータ構造とキー関数を説明します.彼がどのように合併を実現したのかを見てみます.
JDK 1.7中の実現
JDK 1.7のConcerenthashMapはセグメントロックの設計を採用しています.まずデータ構造を見てみます.ConcerenthashMapにはsegment配列が含まれています.各segmentにはもう一つのHash Entry配列が含まれています.つまり、各segmentには完全なhashtableが含まれています.上記のsegment構造の定義を見てみましょう.
次に、ConcerenthashMapのいくつかのキー関数を見てみます.put、get、rehash、size方法は彼がどのように合併を実現しているかを見てください.
put方法の実現
putメソッドの呼び出しを追跡します.
次にsegmentのput方法を見てみます.
見ることができます.putの方法はロックをかける必要があります.この時はセグメントロックをかけます.
ゲット方法
rehash方法:
segmentのcount(segment配列で使用されている個数を指す)がthresh Holdより大きい場合は、rehash法を使用して拡大する必要があります.拡張操作もputのロック中にあり、スレッドの安全を保証します.
sizeメソッド:
JDK 1.8の中の実現
JDK 1.8の中で、大きな変化がありました.段鎖を使っていません.Node配列+チェーン+赤と黒の木に変えました.
重要な変数があります.sizectl負数は、初期化または拡張が行われていることを示し、−1は初期化中であり、−NはN−1スレッドが拡張されていることを示している. 正数0は、まだ初期化されていないことを示している.他の正数は次の拡大サイズを表します. まずコアデータ構造を見てみます.
ForwardingNode、拡張機能を使用したチェーン表、拡張機能を使用して、このnodeを経験したら、他にもこのnodeを拡大しています.スキップすればいいです
CAS操作
このバージョンはCAS操作が多く使われています.CASとは、メモリに対応するエリアの値を比較して、期待値と同じではないかということです.等しいなら、新しい値を設定して入れます.一般的にこのように使用されて、まず対象のドメインの値を取得し、この値を期待値としてCASアルゴリズムを起動する.
コンカレントHashMapには三つのコアのCAS操作があります.tabAt:配列中位置i上のノードcas TabAtを取得する:配列位置i上のノードsetTabAtを設定する:volatileを利用して位置i上のノードを設定する.
いくつかのポイントを紹介します.
initTable
拡充方法transfer
ConccurrenthashMapでの配列使用数が閾値より大きい場合は、拡張が必要です.ここの拡大容量は2つの部分に分けられています.1.シングルスレッド処理で、newTableを新規作成します.容量が元の2倍になります.2.マルチスレッド処理は、元のテーブルのデータをnewTableにコピーする.
マルチスレッド処理のロジック:は、tabAtを利用してiの位置を取得する. この位置が空の場合、ロックをかけずにforwardノードに設定します. 普通のノードであれば、ロックをかけて分析し、newTableのiとi+nの位置に置いて、処理が終わったら、このノードをforwardに設定します. putメソッド
ロジックが複雑ですので、コードを付けません.流れを教えてください.1.テーブル==nullの場合は、上記の初期化を呼び出します.2.テーブルの中のiの位置が空いているなら、ロックをかけずに新しいnodeを作ってcasの方式で入れます.3.当該Nodeが拡大している場合は、拡張機能を助け、helpTransfer関数を呼び出す必要があります.4.正常に添加するとロックが必要です.synchronizedを使って、衝突があれば、判断が必要です.チェーンの長さが8より大きいとき、チェーンを赤と黒の木に変えます.
ゲット方法
get方法はロックをかけない.CAS操作により、ロックなしのアクセスが可能です.mapが拡大している時に、forwardnodeもfind()の方法を提供して、拡大していることを保証します.対応するvalueも見つけられます.
size()操作も大体の値です.
concurrenthashMapは弱一致で、get、sizeは正しい値を得ることが保証できません.
Conccurrenthashmapはjava併発において重要なクラスであり、HashTableの代わりに、同時進行可能なhashtalbeを実現する.私は1.7と1.8の中の実現をもって、それぞれConcerenthashMapのキーデータ構造とキー関数を説明します.彼がどのように合併を実現したのかを見てみます.
JDK 1.7中の実現
JDK 1.7のConcerenthashMapはセグメントロックの設計を採用しています.まずデータ構造を見てみます.ConcerenthashMapにはsegment配列が含まれています.各segmentにはもう一つのHash Entry配列が含まれています.つまり、各segmentには完全なhashtableが含まれています.上記のsegment構造の定義を見てみましょう.
static final class Segment extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
... ...
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel)
次に、ConcerenthashMapのいくつかのキー関数を見てみます.put、get、rehash、size方法は彼がどのように合併を実現しているかを見てください.
put方法の実現
putメソッドの呼び出しを追跡します.
public V put(K key, V value) {
Segment s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
次にsegmentのput方法を見てみます.
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry first = entryAt(tab, index);
for (HashEntry e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
見ることができます.putの方法はロックをかける必要があります.この時はセグメントロックをかけます.
ゲット方法
public V get(Object key) {
Segment s; // manually integrate access methods to reduce overhead
HashEntry[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
rehash方法:
segmentのcount(segment配列で使用されている個数を指す)がthresh Holdより大きい場合は、rehash法を使用して拡大する必要があります.拡張操作もputのロック中にあり、スレッドの安全を保証します.
sizeメソッド:
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
final Segment[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
JDK 1.8の中の実現
JDK 1.8の中で、大きな変化がありました.段鎖を使っていません.Node配列+チェーン+赤と黒の木に変えました.
重要な変数があります.sizectl
static class Node implements Map.Entry {
final int hash;
final K key;
volatile V val;
volatile Node next;
}
ForwardingNode、拡張機能を使用したチェーン表、拡張機能を使用して、このnodeを経験したら、他にもこのnodeを拡大しています.スキップすればいいです
CAS操作
このバージョンはCAS操作が多く使われています.CASとは、メモリに対応するエリアの値を比較して、期待値と同じではないかということです.等しいなら、新しい値を設定して入れます.一般的にこのように使用されて、まず対象のドメインの値を取得し、この値を期待値としてCASアルゴリズムを起動する.
コンカレントHashMapには三つのコアのCAS操作があります.tabAt:配列中位置i上のノードcas TabAtを取得する:配列位置i上のノードsetTabAtを設定する:volatileを利用して位置i上のノードを設定する.
いくつかのポイントを紹介します.
initTable
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;
}
拡充方法transfer
ConccurrenthashMapでの配列使用数が閾値より大きい場合は、拡張が必要です.ここの拡大容量は2つの部分に分けられています.1.シングルスレッド処理で、newTableを新規作成します.容量が元の2倍になります.2.マルチスレッド処理は、元のテーブルのデータをnewTableにコピーする.
マルチスレッド処理のロジック:
ロジックが複雑ですので、コードを付けません.流れを教えてください.1.テーブル==nullの場合は、上記の初期化を呼び出します.2.テーブルの中のiの位置が空いているなら、ロックをかけずに新しいnodeを作ってcasの方式で入れます.3.当該Nodeが拡大している場合は、拡張機能を助け、helpTransfer関数を呼び出す必要があります.4.正常に添加するとロックが必要です.synchronizedを使って、衝突があれば、判断が必要です.チェーンの長さが8より大きいとき、チェーンを赤と黒の木に変えます.
ゲット方法
get方法はロックをかけない.CAS操作により、ロックなしのアクセスが可能です.mapが拡大している時に、forwardnodeもfind()の方法を提供して、拡大していることを保証します.対応するvalueも見つけられます.
size()操作も大体の値です.
concurrenthashMapは弱一致で、get、sizeは正しい値を得ることが保証できません.