ソースコード解釈のHashMap部分

HashMap

HashMapはキー・バリュー・データ構造で、jdk1.7ではその基礎となるデータ構造は連鎖表＋配列、jdk1.8ではそのデータ構造は連鎖表＋配列＋赤黒木です。

赤黒木を導入した理由は、jdk1.7ではチェーンテーブルの長さが長すぎると、チェーンテーブルのクエリパフォーマンスに影響するからです。

ローディングファクターが0.75なのはなぜですか？

• 負荷率を相対的に大きく設定すると、拡張の閾値が高くなり、拡張頻度が低くなり、メモリ消費量が少ないと言われていますが、ハッシュ競合の可能性が高くなります。比較的大きく設定すると、要素の動作時間が長くなり、動作効率が悪くなります。

• 負荷率を相対的に小さく設定すると、拡張の閾値が相対的に低くなり、メモリ占有量が相対的に大きくなり、格納要素が相対的に疎になり、ハッシュ競合の可能性が相対的に小さくなり、演算性能が相対的に高くなります。

• メモリとパフォーマンスの妥協点を作るため、0.5と1の間の中央値0.75が負荷因子として選ばれました。

HashMapのクエリーメソッドget(key)のソースコードは以下の通りです：

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;
//配列が空であるか、配列の長さが0であるか、ハッシュ値がチェインテーブルの最初の要素に対応するNULLである場合に返す。null
 if ((tab = table) != null && (n = tab.length) > 0 &&
 (first = tab[(n - 1) & hash]) != null) {
//キーのチェックサムを通して、最初のエレメントがエレメントかどうかをチェックする。
//1.hash 2.key
 if (first.hash == hash && 
 ((k = first.key) == key || (key != null && key.equals(k))))
 return first;
//最初のノードがtreenode型でなければ、次のノードに進み、最初のノードがtreenode型かどうかを判断する。
 if ((e = first.next) != null) {
 if (first instanceof TreeNode)
//最初のノードがtreenode型であれば、赤黒木を使ってそのノードが探すべきノードかどうかを判断する。
 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//それ以外の場合は、チェーンテーブルのメソッドに従って判断する。
 do {
//エントリーがキーに属する場合、2つの条件を満たす必要がある。1.hashの値は等しい。2.key 
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 } while ((e = e.next) != null);
 }
 }
 return null;
}

取得方法のまとめ

キーに対応する値を照会る場合は、まずキーに対してハッシュを行い、ハッシュ値を取得します。

• ステップ1：最初に配列が空か、または**ハッシュ値に対応する配列位置の最初の要素がNULLかどうかを判断します。**これらの両方が真であれば、NULLを返し、このキーに対応する値がないことを示します；
• ステップ2：最初のステップでnullを返さなかった場合、ハッシュ値に対応する配列位置の最初の要素がキーチェックで調べる要素であるかどうかをチェックし、判定が有効であれば配列位置の最初の要素を返します；
• ステップ 3: ステップ 2 が成立しない場合、最初の要素の後に後継要素があるかどうかを判定します。ない場合もnullを返し、このキーに対応する値がないことを示します。ある場合は、まず最初のノードのタイプを判断し、最初のノードが赤黒木のノードタイプであれば、赤黒木のメソッドgetTreeNodeを使用して、このキーに対応する値の値を見つけ、最初のノードがチェーンリストのノードタイプであれば、チェーンリストの終わりまで、ノードのキーがクエリキーと同じかどうかを判断するために循環し続け、そうでない場合はnullを返します。最初のノードがチェーン・テーブルのノード・タイプである場合は、チェーン・テーブルの終わりまで、ノードのキーがクエリのキーと同じかどうかを判断するために循環し続け、存在しない場合は null を返します。

HashMapのクエリメソッドput(key,value)のソースコードは以下の通りです：

public V put(K key, V value) {
 return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node<K,V>[] tab; Node<K,V> p; int n, i;
//ハッシュテーブルが空の場合、初期化する
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
//もしあなたの場所に連鎖テーブルがなければ、直接挿入することができる。
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 else {
 Node<K,V> e; K k;
//ハッシュテーブルの最初の要素がキー値に対応する要素である場合、つまりハッシュ値とキーが等しい場合、ハッシュテーブルをトラバースすることができる。
//で、キーに対応する要素を上書きする。
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
//それ以外の場合は、ノードの種類に応じて、赤黒木か連鎖表かを判断する。
//赤黒木を直接キーと値のペアにする
 else if (p instanceof TreeNode)
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 else {
 for (int binCount = 0; ; ++binCount) {
//循環判定
 if ((e = p.next) == null) {
//キーに対応する要素がない場合は
 p.next = newNode(hash, key, value, null);
//チェインテーブルの長さが8を超えると、赤黒木になる。
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
//要素に対応するキーを持ち、それを
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
//取り出した後、値を更新し、古い値を返す
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
//ハッシュテーブルの長さが>threshold展開時
 if (++size > threshold)
 resize();
 afterNodeInsertion(evict);
 return null;
}

方法論の要約：

キーと値のペアを置く場合は、まずキーをハッシュしてハッシュ値を取得します。

• ステップ1：ハッシュテーブルが空の場合は初期化；
• ステップ2：キーのハッシュ値とハッシュテーブルの長さから1を引いたwith操作の場合、この位置に要素がなければ、直接挿入してnullを返し、size>thresholdの場合、つまり、ハッシュテーブルの長さが配列展開のための展開しきい値よりも大きいsize++の場合、この位置の要素がキー値に対応する要素である場合、つまり、ハッシュ値が等しく、キーが等しい==の場合、値に対応するこのキーを上書きし、古い値を返します。そして、このキーに対応する値を上書きし、古い値を返します；
• ステップ3：ステップ2が成立しないことを前提に、最初の要素のノードタイプが赤黒木ノードか連鎖表ノードかを判断し、赤黒木ノードであれば、赤黒木のputTreeValメソッドを使用して対応するキーと値のペアを挿入し、連鎖表ノードであれば、連鎖表上のノードをループします ステップ4：ステップ3が成立しないことを前提に、最初の要素のノードタイプが赤黒木ノードか連鎖表ノードかを判断し、赤黒木ノードであれば、赤黒木のputTreeValメソッドを使用して対応するキーと値のペアを挿入します；
• ステップ4：対応するキーを持つノードがない場合は、新しいノードを作成し、チェーンテーブルの末尾に追加し、結合後、チェーンテーブルの長さが8より大きいかどうかを判断します。
• 注：プロセス全体を通して、直接挿入、つまり、ハッシュテーブルの場所に要素がないときにのみ、直接結合は、新しい場所が要素を格納するために開かれるため、ハッシュテーブルを展開するかどうかを決定する必要がある、サイズ+ +。

HashMapのクエリーメソッドresize()のソースコードは以下の通りです：

final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table;
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 int oldThr = threshold;
 int newCap, newThr = 0;
 if (oldCap > 0) {
 if (oldCap >= MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return oldTab;
 }
//拡張容量は現在の容量の2倍で、最大容量は超えない。
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
 newThr = oldThr << 1; // double threshold
 }
 else if (oldThr > 0) // initial capacity was placed in threshold
 newCap = oldThr;
 else { // zero initial threshold signifies using defaults
 newCap = DEFAULT_INITIAL_CAPACITY;
 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 if (newThr == 0) {
 float ft = (float)newCap * loadFactor;
 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 (int)ft : Integer.MAX_VALUE);
 }
 threshold = newThr;
 @SuppressWarnings({"rawtypes","unchecked"})
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
//元のハッシュテーブルが空ではない、つまり初期化されたハッシュテーブルではない
 if (oldTab != null) {
//オリジナルのハッシュテーブル長トラバーサルによると
 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);
//連鎖テーブル型の場合、JDK8最適化セクション
 else { // preserve order
 Node<K,V> loHead = null, loTail = null;
 Node<K,V> hiHead = null, hiTail = null;
 Node<K,V> next;
 do {
 next = e.next;
//もし要素のハッシュ値と古いハッシュテーブルの容量が0
//チェインテーブルの先頭はloHead、末尾はloTail
 if ((e.hash & oldCap) == 0) {
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 }
//もし要素のハッシュ値と古いハッシュテーブルの容量が1
//チェーンテーブルの先頭をhiHead、末尾をhiTail
 else {
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
//low連鎖テーブルはハッシュ・テーブルの元の場所に残っており、高位連鎖テーブルはハッシュ・テーブルの元の場所に移動している+元のハッシュテーブルの容量
 if (loTail != null) {
 loTail.next = null;
 newTab[j] = loHead;
 }
 if (hiTail != null) {
 hiTail.next = null;
 newTab[j + oldCap] = hiHead;
 }
 }
 }
 }
 }
 return newTab;
}

リサイズ方法のまとめ：

リサイズ・メソッドは、主にハッシュ・テーブルの初期化や拡張を行います。

• ハッシュ・テーブルが空の場合、oldCap=0、oldThr=0になります。oldThrが0になり、定義された位置に戻る理由については、javadocに記載されています：

Additionally, if the table array has not been allocated, this field holds the initial array capacity, or zero signifying DEFAULT_INITIAL_CAPACITY.)

訳注：さらに、テーブル配列が割り当てられていない場合、このフィールドは初期配列容量を保持するか、DEFAULT_INITIAL_CAPACITYの値が0であることを示します。 主文の後半は、DEFAULT_INITIAL_CAPACITYの値が0であることを示しています。

• 最初のステップは、配列が空のときにnewCapとnewThrに直接値を代入することです：

  newCap = DEFAULT_INITIAL_CAPACITY; //初期値は16です。

• 補足：配列が空の場合、別の状況がある、つまり、HashMapは長い間作成されているが、すべての要素を削除すると、配列はnullですが、oldThr>0（つまり、次のifの判断に）：この時点で、古い拡張しきい値の配列の容量の拡張後、新しい配列の容量とそれの積と負荷率は、最大容量よりも小さい場合、新しい拡張しきい値はftです。そして，新しい配列の容量と負荷率の積がともに最大容量より小さい場合，新しい拡張閾値は ft となり，最後に配列が空であるため，拡張された新しい配列がそのまま返されます．

  else if // 初期容量がしきい値に置かれていた newCap = oldThr; if { float ft = newCap * loadFactor; newThr = MAXIMUM_CAPACITY ?ft : Integer.MAX_VALUE); }.

• ハッシュ・テーブルが空でない場合、oldCapとoldThrはともに>0です。

  if (oldCap > 0) {
   if (oldCap >= MAXIMUM_CAPACITY) {
   threshold = Integer.MAX_VALUE;
   return oldTab;
   }
   else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
   oldCap >= DEFAULT_INITIAL_CAPACITY)
   newThr = oldThr << 1; // double threshold
   }
  

• もしそうでなければ、新しいハッシュテーブルの容量はoldCap << 1、つまり古いハッシュテーブルの容量は拡張の容量の2倍になります。DEFAULT_INITIAL_CAPACITY の場合、newThr = oldThr << 1、つまり、拡張のしきい値も元の2倍になります。

• 2番目のステップでは、配列の再配置の要素は、元のハッシュテーブルの走査の長さに応じて、要素のハッシュテーブルの位置で見つかったときに空ではない、要素の位置を記録し、ハッシュテーブルが1つだけの要素の位置に配置されているときに、空になります他の位置に新しいハッシュテーブルに再ハッシュされるか、またはその方法：、1つだけの要素ではない場合、3番目のステップに対処するために。

• ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);第3ステップでは、最初のノードが赤黒木ノードかどうかを判断し、赤黒木ノードであれば赤黒木に従って分割し、そうでなければ連鎖リスト処理法を使用して第4ステップに進みます。

• 第4ステップでは、要素のハッシュ値と演算を行った後の古いハッシュテーブルの容量が0に等しい場合、要素は低チェーンテーブルに配置され、チェーンテーブルのヘッドはloHead、テールはloTailです;要素のハッシュ値と演算を行った後の古いハッシュテーブルの容量が1に等しい場合、要素は高チェーンテーブルに配置され、チェーンテーブルのヘッドはhiHead、テールはhiTailです。

• 第5ステップでは、LOWチェインテーブルはハッシュテーブルの元の位置にあり、HIGHチェインテーブルは元のハッシュテーブルの位置＋元のハッシュテーブルの容量の位置に移動します。newTab[j + oldCap] = hiHead;拡張が完了すると、新しいハッシュテーブルが返されます。

チェーンテーブルの長さ≧8、配列の長さ≧64の場合、チェーンテーブルは赤黒木に変換され、配列の長さ＞拡張しきい値のしきい値の場合、拡張が実行されます。

• 対応するリンクされたテーブルを見つける方法

キーのハッシュ値はハッシュ化され、配列の長さは-1。

• JDK1.7のHashMapがデッドループに陥る理由

ハッシュマップは配列＋連結テーブルを使っています。配列は固定長で、連鎖表は長すぎるため、リハッシュによって連鎖表の長さを短くするために配列の長さを拡張する必要があります。2つのスレッドが同時に拡張をトリガーした場合、ノードを移動すると2つのノードの連鎖表が互いに参照され、円形の連鎖表が生成されます。

• jdk1.8 HashMapがマルチスレッドの場合、デッドループの問題が発生します。

スレッドセーフの問題は、連鎖したテーブルをツリーに変換するときや、ツリーに対して操作を実行するときに発生します。両方の TreeNode ノードが互いに親参照を持っています。

複数のスレッドが共有データを用いて並列に実行されるプログラムにおいて、スレッドセーフコードは、同期メカニズムを通じて、各スレッドがデータ汚染などの予期せぬ事態に陥ることなく、適切かつ正しく実行できることを保証します。

• なぜHashMapの長さは2のべき乗なのですか？

hash%length hash&(length-1)ハッシュするとき、配列の添え字は & ハッシュで計算されます。ハッシュ値は、配列の長さに乗じて計算されます。

• HashMap作成時にコンストラクタに渡された長さが2のべき乗でない場合はどうなりますか？

this.threshold = tableSizeFor(initialCapacity);コンストラクタでは、initialCapacity に対して tableSizeFor が実行されます。

なぜ tableSizeFor の値を threshold に代入するのですか？HashMap に対して初めて put 操作が実行されると、resize メソッドが呼び出されます。

• HashMapをトラバースする一般的な方法にはどのようなものがありますか？

1、イテレータ・ウェイ・トラバーサル

//entrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
 while (iterator.hasNext()) {
 Map.Entry<Integer, String> entry = iterator.next();
 System.out.print(entry.getKey());
 System.out.print(entry.getValue());
 }
//keySet
Iterator<Integer> iterator = map.keySet().iterator();
 while (iterator.hasNext()) {
 Integer key = iterator.next();
 System.out.print(key);
 System.out.print(map.get(key));
 }

2、縦断の場合

//entrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
 System.out.print(entry.getKey());
 System.out.print(entry.getValue());
 }
//keySet
for (Integer key : map.keySet()) {
 System.out.print(key);
 System.out.print(map.get(key));
 }

3、ラムダ式

map.forEach((key, value) -> {
 System.out.print(key);
 System.out.print(value);
 });

4.ストリームAPI

//  
map.entrySet().stream().forEach((entry) -> {
 System.out.print(entry.getKey());
 System.out.print(entry.getValue());
 });
// 
map.entrySet().parallelStream().forEach((entry) -> { System.out.print(entry.getKey()); System.out.print(entry.getValue()); });