前置き

以前は実装原理を細かく理解し、ソースコードを読み込んでいました。しかし、jdkのバージョンアップが急速に繰り返され、ついに主流はJDK7からJDK8へ。

JDKの前方互換性のため、JDK8を使う過程で特別なことは見つからず、機能も変わりませんでした。しかし最近、気になってIDEをクリックしてやり方を確認したところ、ちょっと混乱しました。なぜ記憶と違うのか？JDK7からJDK8へのアップグレードがあったのでしょうか？何がアップグレードされ、何がアップグレードされたのでしょうか？

この好奇心で、JDK7とJDK8のソースコードをひっくり返して、2つの実装の原理は、約半年かそこらの速度のJDKバージョンの比較を行うには、新しいプッシュするには、もちろん、認知も継続的な学習についていく必要がある、波の上に立って、さもなければ、泥や石の流れの溺れ人質に情報の転がる泥や石になります。

マップファミリーのリレーションシップ階層を最初に表示することで、その後の理解が深まります。

入門の基本的な知識は、あまり長文になることはありません、ポイントにまっすぐ、JDK7とJDK8の機能の実装を見てください。

まず、JDK7 の HashMap の基本的な実装です。

基本

1.7、1.8に関係なく、HashMapの実装フレームワークは方法の組み合わせです。その構造を以下に示します：

通常、最も使用することは、操作は、根本的な実装を理解したい、最も直接的な方法から見ることです。しかし、具体的にソースコードを見る前に、まずいくつかのドメイン変数に焦点を当て、次のように、基礎を再生します：

上の図では、各変数を簡単に説明しています。 もう一つ、最後の変数は、マップがk-vペアを追加/削除した回数や内部構造を調整した回数を記録します。この変数の主な機能は、マップの操作の一貫性チェックを行うことで、イテレータの操作中にマップの値が変更された場合、例外が直接スローされます。

また、上記のドメイン変数に方程式があることにも注意が必要です：

threshold = table.length * loadFactor;

新しい値を入れる操作が行われると、対応するキーがすでにマップに存在する場合は置き換えられますが、存在しない場合は、まずそのキーが有効かどうかを判断します。これは、ハッシュテーブルを拡張するかどうかを決める重要な要素です。

レベルの使用の面では、メソッド、メソッドよりもほとんどのメソッドの使用。詳細な動作原理を理解したい場合は、最初に2つのメソッドからそれを参照して、これらの2つのメソッドを理解することも、基本的にHashMapの実装原理を明確にすることができます。

put()メソッド

上記の変数と使い方が理解できたら、次にメソッドの具体的な実装を見てみましょう：

上のスクリーンショットに示すように、プットメソッド全体の処理は4つの部分に分けることができます：

上のスクリーンショットのメソッドには戻り値があり、シナリオは以下のように区別されていることにお気づきでしょうか：

• シナリオ1：put操作が実行される前にキーがすでに存在していた場合、put操作が実行されると、新しい値が前の操作の古い値を上書きするために使用され、古い値が返されます；
• シナリオ 2: キーが存在しない場合は、null 値を返します。

以下は、プット・メソッドの各パートの詳細な内訳です。

特殊なキー値の取り扱い

まず結論ですが、HashMapはkey,valueがnullでもOKで、nullのkeyはカバレッジのvalueに複数のストレージのコピーが格納されるだけです。nullのkeyの格納場所は、バケットの添え字、つまりチェーンテーブルのtable[0]の位置に一律に配置されます；key=nullで初めてput操作を行う場合、table[0]に新しいEntryノードを追加し、ヘッダ挿入メソッドを使用してチェーンテーブルの挿入を行います。

アップコード

private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
}
/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket. It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
 if ((size >= threshold) && (null != table[bucketIndex])) {
 resize(2 * table.length);
 hash = (null != key) ? hash(key) : 0;
 bucketIndex = indexFor(hash, table.length);
 }
 createEntry(hash, key, value, bucketIndex);
}
/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization). This version needn't worry about resizing the table.
 *
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
}

まずチェーンテーブルの位置を選択し、次にチェーンテーブルの走査を行い、もしnullのキーを持つノードがあれば、古い値を新しい値に置き換え、古い値を返し、見つからなければnullのキーを持つ新しいEntryノードを追加します。

つ目の方法に注目してください。 これは一般的な方法です：

ハッシュ、キー、値、バケット添え字が与えられると、新しいEntryノードが追加されます。ハッシュテーブルに格納されているk-vペアの数が現在の閾値()を超え、現在のバケット添え字が連鎖したテーブルを持つ場合、拡張処理を行います。拡張後、ハッシュは再計算され、新しいバケット添え字が取得され、ヘッダ挿入を使用して新しいノードが追加されます。

拡張

前のセクションで述べたように、k-vペアの容量がある限界を超えると、ハッシュテーブルを拡張する必要があります。では、どのようにして拡張するのでしょうか？ 以下にソースコードを示します：

スケーリング後のサイズは、スケーリング前のサイズの2倍です；

oldCapacity=table.length;
newCapacity = 2 * oldCapacity;

旧テーブルから拡張後の新テーブルへのデータ再配置。 衝突の多発を避けるため、まずEntryテーブルの各ノードをハッシュし直す必要があるかどうかを判断し、ハッシュ値に基づいてバケットの添え字を計算し、ヘッダ補間法を用いてノード再配置を行います。

バケット添え字の計算方法は？

ハッシュ値の計算

方程式への入力として、キーのhashCodeを使用して、ハッシュの値：まず第一に、そこにキーのハッシュ値でなければなりませんが、整数、int型であり、計算は衝突アルゴリズムを最小限に抑えるための方法を使用して、特定の原則は、限り、あなたが行に少し知っているように、展開されません。

以上の知識から、人は

ここにはもうひとつ知識が必要です。HashMapのキーの型については、以下の条件を満たす必要があります：

論理的等価性の意味はもう少し広く、同じメモリ・アドレスを持つ2つのオブジェクトとして定義することもできますし、あるドメインの値が等しいオブジェクトとして定義することもできます。 クラスの例として、以下のコードを参照してください：

String str1 = "abc";
String str2 = new String("abc");
System.out.println(str1 == str2); // false2つのオブジェクトは同じメモリアドレスを持っていない。
System.out.println(str1.equals(str2)); // true どちらのオブジェクトも同じフィールド値を持ち、abcという文字を格納している。

上記のコードにある2つのオブジェクトは、メモリ・アドレスは異なりますが、クラスのメソッドのオーバーライド()に従ってドメイン変数に文字'a'、'b'、'c'が格納されているため、両オブジェクトは論理的に等しくなります。2つのオブジェクトは論理的に等しいので、次のようになります：

System.out.println(str1.hashCode() == str2.hashCode());
--- ---
true

そこから、同じHashMapオブジェクトでは、次のような結果が生じることが分かっています：

String str1 = "abc";
String str2 = new String("abc");
Map<String, Integer> testMap = new HashMap<>();
testMap.put(str1, 12);
testMap.put(str2, 13);
String str3 = new StringBuilder("ab").append("c").toString();
System.out.println(testMap.get(str3));
--- ---
13

また、逆に考えてみてください。

HashMapのキーが上記の条件を満たさないとします。つまり、2つのオブジェクトが等しい場合、それらのhashCodeは同じではないかもしれません。では、これはどのような結果をもたらすのでしょうか？上記のコード例では、例えば、それらのhashCodeが等しくない場合、対応するハッシュが等しくない可能性があり、testMapは、別のバケツに割り当てられるために操作を置く、その結果、最も直接的な結果は、それが二回保存されます。間接的な結果はさらに多く、たとえば、あるオブジェクトを使用して操作を実行すると、その値を取得できないことがあります。

したがって、HashMapのキーに対応する型は以下の条件を満たす必要があります：

モードフェッチの論理

ハッシュ値の計算を分析した次のステップは、バケット添え字の計算です：

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
 return h & (length-1);
}

テーブルの容量とハッシュ値に対して""演算を行い、ハッシュ化されたテーブルのバケット添え字を取得します。

3. 拡張

このような平凡な、そしてそうでない計算は誰にでも理解できることですが、なぜ必要なのでしょうか？その背景にある考え方は？下の説明を見る前に、考えてみてください～。

ドキュメントの冒頭で、HashMapクラスの各ドメイン変数が示されています。このうち、ハッシュテーブルの初期サイズはデフォルトで2のべき乗である16に設定されています。その後、サイズを拡張するときは2の倍数にして拡張します。なぜハッシュテーブルのサイズを2のべき乗に制御する必要があるのでしょうか？

ハッシュがより均一であるように：衝突の確率を低減します。バケツの添え字の位置を計算するために、キーのハッシュ値によると、"with "式の使用：h＆、ハッシュテーブルの長さが2のべき乗である場合、モジュラスのハッシュ値のテーブルの長さの使用に相当する、ハッシュがより均一である;：テーブルの長さが2のべき乗である場合、バイナリの最後のビットが1でなければならない、"with "操作のハッシュ値では、最後のビットが1である可能性があり、0である可能性があり、言い換えれば、モジュラスの結果は1と0の両方を持っている、言い換えれば、両方の衝突の結果。2進数の最後の桁は1でなければならず、ハッシュ値に対して "with "演算を行う場合、最後の桁は1にも0にもなります。言い換えれば、モデル化の結果は偶数にも奇数にもなり得ます。 もし値が偶数であれば、ハッシュ演算後の値は0にしかならないと想像してください。 奇数の添え字を持つバケツは決してハッシュ化されず、スペースの半分が無駄になります。

ターゲットバケット内のエントリーノードのトラバース

まずはこの部分を取り出してみましょう：

...
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
}
...

このハッシュ値から添え字を計算し、対応するターゲットバケットを見つけ、チェインテーブルのトラバーサル演算を行い、以下のように1つずつ比較します：

ノードのキーがターゲット・キーとメモリ・アドレスまたは論理的に等しく、2つのうちどちらかが満たされていること。

put()メソ

この方法に比べ、実装は比較的簡単です。まず、キーのハッシュ値から対象となるバケツの添え字を計算し、対応するバケツのチェインテーブルを走査して一つずつ比較し、結果を得ます。

public V get(Object key) {
 if (key == null)
 return getForNullKey();
 Entry<K,V> entry = getEntry(key);
 return null == entry ? null : entry.getValue();
}
/**
 * Returns the entry associated with the specified key in the
 * HashMap. Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 }
 return null;
}

マップ内のイテレータ

マップ走査のいくつかの方法

まずは質問から。 地図を縦断する方法をいくつ思いつきますか？

方法1：イテレーター

Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<String, Integer> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
}

後述するように、ハッシュテーブルの各バケットの各Entryノードを1つずつ取得します。

方法2：使用する最も一般的な方法は、同時にキー、値の値を取得することができます

//  
for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
 System.out.println(entry.getKey() + ":" + entry.getValue());
}

この方法は、デコンパイルコマンドjavapやIDEでコンパイルされたステートメントを検索するために使用できる構文糖です：

Iterator var2 = testMap.entrySet().iterator();
while(var2.hasNext()) {
 Entry<String, Integer> entry = (Entry)var2.next();
 System.out.println((String)entry.getKey() + ":" + entry.getValue());
}

Iteratorの機能はそのまま使っています。

方法3：foreachを使う

testMap.forEach((key, value) -> {
 System.out.println(key + ":" + value);
});

これはラムダ式です。foreachも構文糖で、内部的にはprocessingメソッドを使いますが、Mapのforeachメソッドは以下のように実装されています：

方法4：キーの集合を繰り返し処理

Iterator<String> keyIterator = testMap.keySet().iterator();
while (keyIterator.hasNext()) {
 String key = keyIterator.next();
 System.out.println(key + ":" + testMap.get(key));
}

これもイテレータのアプローチですが、Setクラスを介したイテレータです。

値の取得で、この方法と比較して、また、道を通過する必要がありますが、パフォーマンスと比較してはるかに低いです。しかし、2つのシーンの独自の用途があり、マップのトラバーサルのみキーを使用する場合は、より適している、値を使用する必要がある場合は、使用することをお勧めします。

これまでの総括から、モード4にも以下のようなバリエーションがあることがわかります：

for (String key : testMap.keySet()) {
 System.out.println(key + ":" + testMap.get(key));
}

まとめると、Mapをトラバースする際に、パフォーマンスの観点から、キーと値の両方を使用する必要がある場合は使用することをお勧めします。いずれにせよ、セカンダリクエリを追加することになるので、使用はお勧めできません。

さらに、これを使用する際には、後述するリムーブ操作を行うことも可能です。

イテレータ実装の原則

まず、クラスとインターフェースの継承関係の図を見てみましょう：

イテレーターはトップレベルのインターフェースで、3つの基本メソッド宣言のみを提供します：

public interface Iterator<E> {
 boolean hasNext();
 E next();
 default void remove() {
 throw new UnsupportedOperationException("remove");
 }
}

これら3つのメソッドも、使わない手はありません。 HashMapでは、1つ目は以下のように新しい内部抽象クラスです：

Entryノードの走査を例にとってみましょう：

Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<String, Integer> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
}

まず、コードの最初の行で、インターフェースの具象実装クラスを探します：

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 public Map.Entry<K,V> next() {
 return nextEntry();
 }
}

とてもシンプルでしょう？メソッドは1つだけで、インターフェイスのnext()メソッドの実装です。メソッドの内部にも、親メソッドである上のスクリーンショットのクラスのnextEntry()メソッドを指す行が1行あるだけです。

イテレータ実装の原則のHashMapはちょうどそうです、とても平易でシンプルです、それはすべてのHashMapの実装を自分のジャックを行いたいですか？まあ、あなたはできます！

フェイルファスト・ポリシー

この2つがどのように関連しているのか、なぜこのような戦略を思いついたのかについてお話ししましょう。

それは何ですか？ウィキペディアで説明されているように、「高速失敗戦略」と呼ぶことができます：

システム設計において、フェイル・ファスト・システムとは、障害を示す可能性のある状態を即座にインターフェイスで報告するシステムのことです。 フェイル・ファスト・システムは通常、欠陥のある可能性のあるプロセスを継続しようとするのではなく、正常な動作を停止するように設計されています。このような設計では、動作中のいくつかの時点でシステムの状態をチェックすることが多いため、障害を早期に検出することができます。このような設計では、動作中のいくつかの時点でシステムの状態をチェックすることが多いので、どんな障害も早期に検出することができます。 障害高速モジュールの責任は、エラーを検出し、その後、エラーを解除することです。フェイルファスト・モジュールの責任は、エラーを検出し、次にシステムの最上位レベルに処理させることです。

また、高速障害システムは、エラーがあるかもしれないプロセスを継続しようとするのではなく、通常のオペレーションを即座に終了するように設計されていることがよくあります。エラーがあるかもしれないプロセスを継続しようとするのではなく、できるだけ早く問題を検出し、現在の実行プロセスを直ちに終了させ、より上位のシステムに処理を任せるということです。

HashMapでは、前述のドメイン変数がhashMapの実装で使用されます。これは、非同期のマルチスレッド並行処理ではよくあることです。Mapを反復処理するとき、ドメイン変数はローカル変数に代入されます。反復処理中に、コンテンツが変更された回数の一貫性チェックを行うために使用されます。このスレッドで他のスレッドや他の操作によってこの Map の内容が変更されると、不整合が発生し、すぐに例外がスローされます。

一例です：

public static void main(String[] args) {
 Map<String, Integer> testMap = new HashMap<>();
 testMap.put("s1", 11);
 testMap.put("s2", 22);
 testMap.put("s3", 33);
 for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
 String key = entry.getKey();
 if ("s1".equals(key)) {
 testMap.remove(key);
 }
 }
}
---- output ---
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.HashMap$HashIterator.nextNode(HashMap.java:1437)
 at java.util.HashMap$EntryIterator.next(HashMap.java:1471)
 at java.util.HashMap$EntryIterator.next(HashMap.java:1469)
 ...

Map要素を削除する正しい姿勢：Iteatorメソッドは1つしかありません。

//  
Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<String, Integer> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
 if (next.getKey().equals("s2")) {
 iterator.remove();
 }
}

ただし、安全に削除できるからといって、マルチスレッドセーフというわけではなく、複数のスレッドが同時に実行される場合、同期メソッドに設定されていないため、すべてのスレッドが上記の操作を行うと、スローされる例外に矛盾が生じる可能性があることにも注意が必要です。 スレッドインセキュリティの発現と回避方法については、後の章で詳しく述べます。

第二に、JDK8ではHashMapの基礎となる実装に

以前はJDK7のHashMapの実装の詳細な分析されている、私はあなたが最適化することができます場所を発見しているかどうかわからない？たとえば、ハッシュテーブルは、チェーンの構造によって生成されたハッシュの衝突のため、データ量が非常に大きい場合は、衝突率は非常にチェーンテーブルの長さの結果をもたらす増加され、クエリのために、パフォーマンスが低く、低くなります。どのようにクエリのパフォーマンスを向上させるには、JDK8 HashMapは、問題を解決するためになっています。

したがって、JDK7に比べて、JDK8のHashMapは、チェーンテーブル構造の最適化を行うには、特定の条件下では、クエリの効率を向上させる赤黒木になります。

JDK8のHashMapの基本的なストレージ構造は以下のとおりです：

JDK7と比較して、JDK8のHashMapは長い連鎖表を赤黒木に変換します。このメソッドの実装を見てみましょう。

put()

この操作をさらに分析する前に、明確にしておくことがあります。基礎となるストレージ構造が調整されたことに加えて、チェーンテーブル・ノードの定義がクラスからクラスへと変更されましたが、カーネルは変更されておらず、理解には影響しません。

まずソースコード：

とても長くて複雑ではありませんか？実際には、それは難しいことではありません、限り、上記の基本的なストレージ構造を覚えて、コードは非常に理解しやすいです。または同じストレージルーチン、最初のキーによると、ハッシュテーブルの添え字を決定するために、対応するバケットを見つけ、チェーンテーブルを横断し、挿入操作を行います。JDK7では、新しいノードが使用されますが、JDK8では、チェーンテーブルの使用は、新しいノードがチェーンテーブルの最後に追加されます。

上記のコードは、理解しやすいように以下のフローチャートに変換されています：

ハッシュテーブルが NULL、もしくは長さが 0 の場合、展開操作；：インデックスに従って目的のバケツを見つけた後、現在のバケツにノードがない場合、直接新しいノードを追加し、バケツに割り当て；：現在のバケツにチェーンテーブルがあり、先頭ノードが一致する場合、直接置換；：現在のバケツが木構造の場合、赤黒木の挿入操作へ；：ステップ①、③、④が成立しない場合、チェーンテーブルの走査操作へ。ステップ①、②、③、④が成立しない場合、連鎖表の走査を行います。 a) チェーンテーブルに一致するノードがあれば値の置換を行い、b) 一致するノードがなければチェーンテーブルの末尾に追加。i) リンクテーブルの長さがTREEIFY_THRESHOLDより大きい場合、赤黒ツリー変換を実行します。 上記の5つのステップの後、現在のMapに格納されているk-vペアの数がペアの数を超えているかどうかを確認し、超えている場合は、再度容量を拡張する必要があります。

赤黒木の変換操作は以下の通り：

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
 int n, index; Node<K,V> e;
 // テーブルが空の場合、またはテーブルの長さがMIN未満の場合_TREEIFY_CAPACITY一つ目は、クラスが変換されるのではなく、直接展開されることである。
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode<K,V> hd = null, tl = null;
 do {
 TreeNode<K,V> p = replacementTreeNode(e, null);
 if (tl == null)
 hd = p;
 else {
 p.prev = tl;
 tl.next = p;
 }
 tl = p;
 } while ((e = e.next) != null);
 if ((tab[index] = hd) != null)
 hd.treeify(tab);
 }
}

put()

拡張のトリガーとなるシナリオは？Mapに格納されているk-vペアの数がしきい値を超えている場合。

一般的な拡張は2つのステップに分かれて、ハッシュテーブルの長さの拡張は、新しいテーブルに移動したデータの古いテーブルです。だから、JDK8では、どのようにHashMapが展開されますか？

ソースコードスニペットをアップ：

...
// ステップ1の長さについてはすでに拡大したので、ここではステップ2であるデータの移行方法に焦点を当てる。
table = newTab;
if (oldTab != null) {
 // nullでないハッシュテーブルの各バケットをループする。
 // なお"++j"古いタブ[0] 
 for (int j = 0; j < oldCap; ++j) {
 Node<K,V> e;
 if ((e = oldTab[j]) != null) {
 oldTab[j] = null;
 // ノードが1つしかない場合は、その場所に格納する
 if (e.next == null)
 newTab[e.hash & (newCap - 1)] = e;
 else if (e instanceof TreeNode)
 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
 else { // preserve order
 // "lo"プレフィックス付きデリゲートはオリジナルのバケットに格納される。"hi"プレフィックス付きデリゲートは、新しいバケット
 // loHead はチェーンの最初のノードを表し、loTailはチェーンの最後のノードを表す。
 Node<K,V> loHead = null, loTail = null;
 Node<K,V> hiHead = null, hiTail = null;
 Node<K,V> next;
 do {
 next = e.next;
 // oldCapを使用する=8  
 //  e.hash=24
 // &  oldCap=8
 // =  --> 0ではない、マイグレーションが必要
 // このパターンは[oldCap, (2*oldCap-1)]の間のデータは
 // また、n*2*oldCap クラス内のデータをすべて移行したい場合は移行する必要があるが、それ以外のデータは移行する必要はない。
 if ((e.hash & oldCap) == 0) {
 // これは順序挿入であり、つまり、元のチェーンテーブルのノードを現在のチェーンテーブルの末尾に順番に追加する。
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 }
 else {
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
 if (loTail != null) {
 loTail.next = null;
 newTab[j] = loHead;
 }
 if (hiTail != null) {
 hiTail.next = null;
 // 再配置が必要なノードの場合、新しい添え字は、現在の添え字からoldCap進んだ距離になる。
 newTab[j + oldCap] = hiHead;
 }
 }
 }
 }
}

get()

上記の put() 操作を理解すると、get() 操作が簡単になります。

public V get(Object key) {
 Node<K,V> e;
 return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 if ((tab = table) != null && (n = tab.length) > 0 &&
 (first = tab[(n - 1) & hash]) != null) {
 if (first.hash == hash && // always check first node
 ((k = first.key) == key || (key != null && key.equals(k))))
 return first;
 if ((e = first.next) != null) {
 if (first instanceof TreeNode)
 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
 do {
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 } while ((e = e.next) != null);
 }
 }
 return null;
}

まず、ハッシュ値を計算するキーによると、さらに計算ハッシュテーブルのターゲットインデックスを取得するには、もし赤黒木のバケット、赤黒木のルックアップ、赤黒木ではない場合、チェーンテーブルをトラバースします。

第三に、HashMapとHashTableはどのような関係ですか？

復習のために、冒頭のグラフをもう一度貼っておきましょう：

共通点と類似点

::

• 要するに、ハッシュテーブル＋リンクテーブルの実装を使うということです。

::

• 階層的には、HashMap と HashTable は共通のインターフェイスを共有しています。また、HashTable は別の抽象クラスを継承しています；
• HashTableはJDK1.0から、HashMapはJDK1.2から存在しています；
• HashTableはスレッドセーフですが、HashMapはスレッドセーフではありません；
• 初期値とさまざまな方法の拡張。 HashTableの11の初期値は、2 * d + 1の元のサイズの拡張。容量サイズは奇数と素数、およびモデリングメソッドの使用に使用され、より均一なハッシュのこの方法。HashTableの長さは2のべき乗ですが、しかし、欠点は、低性能の素数のモジュラスは、設計がより巧妙であり、前のセクションでも述べたように、モジュラスを取るのこの方法は、直接ビット演算を行うには、より良いパフォーマンスです。

public static void main(String[] args) {
 Map<String, Integer> testTable = new Hashtable<>();
 testTable.put(null, 23); // NPEをスローする
 testTable.put("s1", null); // NPEをスローする
}

メソッドのソースコードを見てください：

public synchronized V put(K key, V value) {
 // Make sure the value is not null
 if (value == null) {
 throw new NullPointerException();
 }
 // Makes sure the key is not already in the hashtable.
 Entry<?,?> tab[] = table;
 int hash = key.hashCode();
 int index = (hash & 0x7FFFFFFF) % tab.length;
 @SuppressWarnings("unchecked")
 Entry<K,V> entry = (Entry<K,V>)tab[index];
 for(; entry != null ; entry = entry.next) {
 if ((entry.hash == hash) && entry.key.equals(key)) {
 V old = entry.value;
 entry.value = value;
 return old;
 }
 }
 addEntry(hash, key, value, index);
 return null;
}

ソースコードでは、valueがNULLであることは許されません。もしNULLであれば、NPEが直接スローされます。keyがNULLの場合、ソースコード9行目：int hash = key.hashCode();はNULL操作を行わず、NPEをスローします。

また、抽象クラスDictionaryは、現在では非推奨クラスと見なされていますが、ソースコードのコメントでは以下のように記述されています：

<strong>NOTE: This class is obsolete. New implementations should
implement the Map interface, rather than extending this class.</strong>

HashMapのスレッド安全性

スレッドの安全性を確保するには、synchronizedキーワードを追加したり、ロック機構を使用したりするなど、いくつかの方法があります。この2つの違いについてはここでは説明しませんが、スレッドセーフに関する次の記事で詳しく説明します。HashTableは前者、つまりsynchronizedキーワードを使用します。

そうすることで、HashTableオブジェクトのスレッドセーフは保証されますが、同時に問題も発生します。なぜ非効率なのでしょうか？同期機能によると、マルチスレッドで共有された重要なリソースのために、同時に唯一のスレッドが占有することができ、他のスレッドが所定の位置で待機する必要があるため、理解を容易にするために、我々は、タイミングを砂時計について考えることを望むかもしれない、最も薄いボトルネックの真ん中は、上記の細かい砂のドロップをブロック同じ理由で、get（）操作を実行するスレッドの数が多い場合、また、このような問題があり、スレッドの数が多い1つずつ処理キューに入れなければなりません。スレッドをキューに入れ、1つずつ処理する必要があります。

この時点で、誰かが言うかもしれないので、取得（）メソッドは、単にデータを取得し、マップとデータの構造を変更していない、行に追加しないでください？申し訳ありませんが、追加しないでくださいすることはできません、他のメソッドが追加され、あなたが追加しないでください、シナリオがあるでしょう、つまり、Aスレッドが配置または削除操作で、Bスレッド、この時点でCスレッドは、操作を取得するために同時に実行することができます、ハッシュテーブルがAスレッドによって変更されている可能性があり、それはまた、問題をもたらすので、追加しないでくださいすることはできません。

さてさて、HashMapはスレッドセーフではない、HashTableはスレッドセーフですが、パフォーマンスが悪い、どのように破るには？使用ConcurrentHashMapクラスは、両方のスレッドセーフだけでなく、効率的な操作は、誰が言った使用。急がない、次のセクションでは、ConcurrentHashMapクラスを詳細に説明します。

第四に、HashMapスレッドの安全でない場所は？

このセクションでは、HashMapにおけるスレッドセキュリティのどのような点が問題を引き起こす可能性があるのかを見ていきます。

データカバレッジの問題

2つのスレッドがput()操作を実行した場合、データの上書きにつながる可能性があります。この問題はJDK7バージョンとJDK8バージョンの両方に存在しますが、ここではJDK7を例にとって説明します。

仮にA、Bの2つのスレッドが同時にput（）操作を実行し、両方のキーが同じbuekctを指して、この時点で2つのノードは、ヘッド挿入を行います。 まず、ここでコードの実装を見てください：

public V put(K key, V value) {
 ...
 addEntry(hash, key, value, i);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
 ...
 createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
}

最後のcreateEntry()メソッドを見てください。最初にバケットの先頭ノードを取得し、次に新しいノードをバケットの先頭として、古い先頭ノードを指して、先頭補間操作を完了します。スレッド A とスレッド B がバケットの先頭ノードを取得したとき、スレッド A のタイムスライスがなくなると、スレッド B はその新しいデータでヘッダ補間操作を完了し、スレッド A の操作の順番になりますが、スレッド A による古いヘッダノードは古くなっており、スレッド A が再度ヘッダ補間操作を行うと、スレッド B が追加した新しいノードは消去され、データが失われます。

実際、put()操作だけでなく、delete操作やmodify操作でもオーバーライドの問題が発生します。

拡大がもたらすデッドループ

また、唯一のJDK7とデッドループの現象の以前のバージョンは、JDK8では、resize（）が連鎖リストの2つのチームを使用するように調整されており、時間内に、マルチスレッドだけでなく、ノードの先頭から再びテール挿入メソッドを行うには、テール挿入メソッドで使用され、デッドループが発生しません。JDK7は、デッドループを引き起こす可能性があるため、resize（）ときにヘッド挿入メソッドの使用は、元の順序は、デッドループの機会を残して、逆に行われるためです。

デッドループのプロセスをさらに説明する前に、JDK7での展開のコード・スニペットを見てください：

void transfer(Entry[] newTable, boolean rehash) {
 int newCapacity = newTable.length;
 for (Entry<K,V> e : table) {
 while(null != e) {
 Entry<K,V> next = e.next;
 if (rehash) {
 e.hash = null == e.key ? 0 : hash(e.key);
 }
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 }
 }
}

実際、これはチェーンテーブルの単純な反転であり、さらに単純化すると、現在のノードeと次のノードe.nextに分割されます。チェーンテーブルa->b->c->nullを例にとると、2つのスレッドAとBがそれぞれ展開操作を行います。

::

スレッド A と B はそれぞれ新しいハッシュ・テーブルを追加し、スレッド B はスレッド A の展開終了後に展開を開始します。このとき、スレッドBでは、現在のノードeはノードaを指し、次のノードe.nextはやはりノードbを指します。このとき、スレッドBでは、現在のノードeはノードaを指し、次のノードe.nextはノードbを指します。ヘッド挿入法によれば、ハッシュテーブルのバケットはaノードを指し、aノードがスレッドBのチェーンテーブルのヘッドノードになります：

スレッドBでaノードがチェーンテーブルの先頭ノードになった後、次のノードe.nextはbノードになります。次のノードe.nextはnullではないので、現在のノードeがbノードになり、次のノードe.nextがaノードになります。ヘッダ挿入を続けると、次のように、bがチェーン・テーブルの先頭ノードになり、nextポインタは古い先頭ノードaを指します：

この時点で、次のノードe.nextはnullではなくノードであり、ヘッダ挿入は続行されます。ポインタが戻され、現在のノードeがノードになり、次のノードがnullになります。aノードがスレッドBのリンクされたテーブルのヘッド・ノードとして使用され、次のポインタは次の図に示すように元の古いヘッド・ノードbを指します：

この時点で、リングリンクされたテーブルが形成されました。同時に次のノードe.nextはnullとなり、処理は終了します。

まとめ

マルチスレッド環境でHashMapを使用すると、あらゆる種類の問題が発生します。上記は、安全性の2つの典型的な例にすぎず、具体的な問題を列挙することはできませんが、次の3つのカテゴリに分類されます：

• デッドループ
• データの重複
• データの重複

JDK1.5では、マルチスレッド環境ではHashTableを使用する傾向がありますが、JDK1.5以降のバージョンでは、同時実行パッケージでマルチスレッド環境専用のクラスが導入され、セグメントロックを使用してスレッドセーフを実現しているため、HashTableに比べてパフォーマンスが高く、推奨されています。

V. HashMapのスレッドセキュリティを回避するには？

前述したように、マルチスレッド環境におけるHashMapは、あらゆる種類の安全でない問題を抱えています。

マップからラッパークラスへの変換

回転させるには？使い方、サンプルコード

Map<String, Integer> testMap = new HashMap<>();
...
// スレッドセーフマップへの変換
Map<String, Integer> map = Collections.synchronizedMap(testMap);

その内部実装も非常にシンプルで、HashTableと同等ですが、現在入力されているマップオブジェクトに対して、新しいオブジェクトがロックされます：

// Collectionsクラスのソースコード
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
 private static final long serialVersionUID = L;
 private final Map<K,V> m; // Backing Map
 final Object mutex; // Object on which to synchronize
 SynchronizedMap(Map<K,V> m) {
 this.m = Objects.requireNonNull(m);
 mutex = this;
 }
 SynchronizedMap(Map<K,V> m, Object mutex) {
 this.m = m;
 this.mutex = mutex;
 }
 public int size() {
 synchronized (mutex) {return m.size();}
 }
 public boolean isEmpty() {
 synchronized (mutex) {return m.isEmpty();}
 }
 public boolean containsKey(Object key) {
 synchronized (mutex) {return m.containsKey(key);}
 }
 public boolean containsValue(Object value) {
 synchronized (mutex) {return m.containsValue(value);}
 }
 public V get(Object key) {
 synchronized (mutex) {return m.get(key);}
 }
 public V put(K key, V value) {
 synchronized (mutex) {return m.put(key, value);}
 }
 public V remove(Object key) {
 synchronized (mutex) {return m.remove(key);}
 }
 public void putAll(Map<? extends K, ? extends V> map) {
 synchronized (mutex) {m.putAll(map);}
 }
 public void clear() {
 synchronized (mutex) {m.clear();}
 }
}

ConcurrentHashMapの使用

クラスはスレッドセーフではないので、スレッドセーフの代替となるクラスを見つけるのは良いアイデアかもしれません。

使用例

Map<String, Integer> susuMap = new ConcurrentHashMap<>();
susuMap.put("susu1", 111);
susuMap.put("susu2", 222);
System.out.println(susuMap.get("susu1"));

使用習慣の面では、HashMapの使用と完全に互換性があります。

JDKバージョン1.5で導入され、java.util.concurrent.Concurrentパッケージの下にあります。

JDK7以前のバージョンでは、クラスはsegmented lockingというテクニックを使っていましたが、jdk8ではsynchronized修飾子も使い返すように大きく変わりました。 この違いについては、今後の記事で詳しく説明します。