公式：HashMapのgetメソッドについて話すなら、getTreeNodeメソッドの具体的な実装について詳しく話すのが一番だ！

序文

ハッシュマップシリーズ

"HashMap "ソースコードのメンバ変数をまだ理解していない？ 早く来い来い!メンバ変数のソースコード解析の整理

" Jerk, Jerk, Jerk, Jerk HashMapのソースコードで再びコンストラクタ・メソッドの落とし穴を踏む"の後編 ！毎度のことですが、何かとお世話になっております。

" MoxiMoxi第3弾 ！HashMapのputメソッドのソースコードをご覧になりましたか？

"HashMapのソースコードは、拡張に加えて、リサイズ拡張メソッドで使用することがありますあなたは本当に知っていますか？

"その5"

"HashMapのremove、getOrDefaultのソースコードを何度も何度も何度も。

「タイトルVI

要素を見つける方法

ケーススタディ - 一般的な検索

@Test
public void test_map_hash_get() {
 HashMap<Integer, String> map = new HashMap<>();
 map.put(1, "aaa");
 map.put(2, "bbb");
 map.put(3, "bbb111");
 String s = map.get(2);
 System.out.println(s);
}

ケーススタディ - 連鎖テーブル検索

@Test
public void test_map_link_get(){
 HashMap<String, Integer> map = new HashMap<>();
 for (int i = 0; i < 64; i++){
 map.put("BB" + i, i);
 }
 System.out.println(map.size());
 map.put("3Qj", 800);
 map.put("2pj", 801);
 map.put("2qK", 802);
 map.put("2r,", 803);
 map.put("3RK", 804);
 map.put("3S,", 805);
 map.put("42j", 806);
 map.put("43K", 807);
 Integer x = map.get("42j");
 System.out.println(x);
}

ケーススタディ - 赤黒ツリー検索

@Test
public void test_map_link_tree(){
 HashMap<String, Integer> map = new HashMap<>();
 for (int i = 0; i < 64; i++){
 map.put("BB" + i, i);
 }
 System.out.println(map.size());
 map.put("3Qj", 800);
 map.put("2pj", 801);
 map.put("2qK", 802);
 map.put("2r,", 803);
 map.put("3RK", 804);
 map.put("3S,", 805);
 map.put("42j", 806);
 map.put("43K", 807);
 map.put("44,", 808);
 
 Integer x = map.get("43K");
 System.out.println(x);
}

ソースコード解析

キーに基づいて対応する値を検索

// キークエリーは、対応するval
public V get(Object key) {
 // ノードを定義する
 Node<K,V> e;
 // キーによってノードがNULLの場合はこのNULLを返し、NULLでない場合は対応する値を返す。
 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) {
 // ツリーが赤黒木かどうかを判断し、赤黒木であれば赤黒木のgetTreeNodeメソッドを呼び出してノードを取得する。
 if (first instanceof TreeNode)
 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
 do {
 // 赤黒木でないなら、連鎖リスト構造で、その連鎖リストにkey
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 // このノードに戻る
 return e;
 } while ((e = e.next) != null);
 }
 }
 // ノードが取得されないnull
 return null;
}

指定されたハッシュとキーに基づいてツリーノードを取得します。

// パラメータhはハッシュ値、パラメータkは指定されたkey
final TreeNode<K,V> getTreeNode(int h, Object k) {
 // ((parent != null) ? root() : this)ノードをフォローする
 // ヒールノードから始まって、指定されたkey
 return ((parent != null) ? root() : this).find(h, k, null);
}

ハッシュと指定されたキーに基づいてノードをクエリします。

// h:ハッシュ値 k: 与えられたkey
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
 // この最初のトラバーサルは、バケット内の最初のノードである
 TreeNode<K,V> p = this;
 // この赤と黒の木をループする
 do {
 int ph, dir; K pk;
 // plドットpが左の子のときはpr ドットpが右の子のときはpr
 TreeNode<K,V> pl = p.left, pr = p.right, q;
 // 現在のポイントのハッシュ値をphに代入し、与えられたハッシュ値が現在のポイントのハッシュ値より小さいかどうかを判断する。
 if ((ph = p.hash) > h)
 // 左の子をp
 p = pl;
 // ポイントのハッシュ値が与えられたハッシュ値より小さい場合
 else if (ph < h)
 // 適切な子供を割り当てるp
 p = pr;
 // ポイントのキーがpkに割り当てられ、pkが与えられたkに等しいときを決定する。
 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
 // 見つけたら、そのまま
 return p;
 // 左の子null
 else if (pl == null)
 // 適切な子供を割り当てるp
 p = pr;
 // 適切な子供向けブログを見極めるnull
 else if (pr == null)
 // 左の子plをp
 p = pl;
 // 比較・計算した結果dir
 else if ((kc != null ||
 (kc = comparableClassFor(k)) != null) &&
 (dir = compareComparables(kc, k, pk)) != 0)
 // 計算されたdirが0より小さければ、plの左の子をpに代入する。p 
 p = (dir < 0) ? pl : pr;
 // 再帰的に検索し、結果を見つけ、それをq
 else if ((q = pr.find(h, k, kc)) != null)
 //  q
 return q;
 else
 // 左の子をp
 p = pl;
 // pが空かどうかを判断し、空でなければループする
 } while (p != null);
 // ノードが直接取得され、返されることはなかった
 return null;
}

getメソッドの実装手順

1キーはハッシュ値によってバケツにマッピングされる。
2バケツにある鍵が探したい鍵なら、それを見つけて返せばいい。
3バケット上のキーが探しているキーでない場合は、後続のノードをチェックする。:
 - 後続のノードが赤黒木のノードであれば、キーに基づいて赤黒木のメソッドを呼び出してそれを取得するvalue
 - 後続のノードが連鎖リスト・ノードである場合、キーに基づき連鎖リストをループすることで得られる。value
4赤黒ツリーを追加した時点で、ツリーの並び順は確保されている。だから、ツリーを調べるときは、基本的にツリーを半分に分けて見ることになる。その方がずっと効率的だ。
5比較ノードのハッシュ値が、調べたいハッシュ値のハッシュ値と等しければ、キーが等しいかどうかを判断し、等しければそのまま返す。等しくない場合は、サブツリーから再帰的に検索する。
 - ツリーの場合は、ツリーの中でkey.equals(k) O(logn)
 - 連鎖リストの場合は、連鎖リストの中でkey.equals(k)見つける、O。

ありがとうございます。

"

• は、質の高いブログを作り続ける私のモチベーションです！==

"