回答編集履歴
1
1116じゃダメでしょ
answer
CHANGED
|
@@ -8,12 +8,12 @@
|
|
|
8
8
|
```
|
|
9
9
|
0: {h: 1000, k: "hoge", v: "fuga"} -> null
|
|
10
10
|
1: {h: 2001, k: "fuga", v: "aaa"} -> {h: 1001, k: "fugafuga", v: "hh"} -> null
|
|
11
|
-
2: {h:
|
|
11
|
+
2: {h: 1106, k: "piyo", v: "zzz"} -> {h: 1106, k: "piyofuga", v: "abc"} -> {h: 18, k: "foo", v: "bar"} -> null
|
|
12
12
|
3: {h: 3, k: "moe", v: "ccc"} -> null
|
|
13
13
|
```
|
|
14
14
|
|
|
15
15
|
"hoge"のvalueを求める場合は、"hoge"のhashは`1000`ですので、`1000 % (4 - 1) = 0`(4はtabelのサイズ)を求めて、インデックスにある{h: 1000, k: "hoge", v: "fuga"}を得ます。そして、hashとkeyが同じであれば、そのvalueを採用します。もし、違っている場合は、次のエントリーを順番に辿ります。他のキーの場合も同様に行います。また、NodeではなくTreeNodeになっている場合があります。この場合は、二分木ですので、二分探索が行われます。どれも同じ物がなく`null`になったときは、エントリー無しとして`null`を返します。
|
|
16
16
|
|
|
17
|
-
一つ注意して欲しいのは、valueを確定するときは、hashとkeyの両方が同じかどうかを見ると言うことです。上の例では2のところにある二つのエントリーでhashが同じです。しかし、"piyofuga"を検索したときは、keyも比較するため、最初のエントリーは採用されず、二つ目のエントリーを返します。
|
|
17
|
+
一つ注意して欲しいのは、valueを確定するときは、hashとkeyの両方が同じかどうかを見ると言うことです。上の例では2のところにある二つのエントリーでhashが同じです(この実装ではhashが衝突しても**問題ありません**)。しかし、"piyofuga"を検索したときは、keyも比較するため、最初のエントリーは採用されず、二つ目のエントリーを返します。
|
|
18
18
|
|
|
19
|
-
さらに細かい動作(どういう風に配列を拡張する
|
|
19
|
+
さらに細かい動作(どういう風に配列を拡張するか、二分木はいつ使われるのか、二分木がどのように実装されているか)は実際のソースコードを確認してみて下さい。
|