質問: ハッシュテーブルの実装についての質問になります。 私の使っている本のハッシュテーブルのところで次のような記述がありました。 「ハッシュテーブルは非常に効率的な検索を行うために、キーを値にマップするデータ構造です。ハッシュテーブルのごく単純な実装には元になる配列とハッシュ関数を用います。オブジェクトとキーを挿入した時、ハッシュ関数はキーを整数値にマッピングし、それは」配列のインデックスを示します。そしてオブジェクトには、そのインデックスに保存されます。 ですが、これは一般的には正しく動作しません。上記の実装では、すべてのキーに対するハッシュ値は一意でなければなりません。そうでなければ誤って配列上のデータを書き換えてしまうかもしれないからです。そのような「衝突」を避けるためには配列は非常に大きなサイズ、それも存在しうるすべてのキーのサイズほどのものを用意しなければなりません。 巨大な配列を作り、キーのハッシュ値をそのままインデックスとする代わりに、ずっと小さなサイズの配列と、ハッシュ値を配列サイズで割った余りをインデックスとした連結リストに保存する方法があります。特定のキーからオブジェクトを得るには対応する連結リストからキーを探索します。 あるいは、二分探索木を使ってハッシュテーブルを実装することもできます。二分探索木の平衡を保つことで、O(log(n))の探索時間を保証することができます。さらに言えば、最初に大きな配列を割り当てる必要も無くなるので、省メモリにもなります。」 後半の二つの実装がよくわかりません。 何がどうなっているのでしょうか。 一つ目の実装(小さなサイズの配列と連結リスト)の場合、オブジェクトはどこにあるのか、キーはどこにあるのか等がよくイメージできません。 二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。 理解できた方、回答お願いします。
回答: 具体的な実装を知りたければ、OpenJDK8 java.util.HashMapのソースを見るのが良いかと思います。OpenJDKでは配列のインデックスと二分探索のハイブリッドな実装のようです。以下、適当に解説します(さらっとしか見てませんので、間違いがあるかも知れません)。 各エントリーは`Node`のオブジェクトとして扱われます。これは、`key`と`value`の他に計算済みの`hash`が含まれます。`hash`は`key.hashcode()`から求められます。そして、もう一つ重要なことに`Node`には`next`があり、片方向連結リストとして構成されるようになっています。さらに`TreeNode`も用意されています。これはそのまま二分木になるように構成されています。 さて、`HashMap`で実際のエントリーが保存されているのは、`Node[]`型の`table`フィールドです。エントリー追加で適当に拡張されます。大きさの余り応じてNodeが連結して入れられるようです。 イメージ的には`table`は下記のようになっています。({h,k,v}はNodeにおける`hash`, `key`, `value`であり、->は`next`が示す次のオブジェクト。実際はTreeNodeの場合もありますし、初めから`null`の場合もあり得ます。) ``` 0: {h: 1000, k: "hoge", v: "fuga"} -> null 1: {h: 2001, k: "fuga", v: "aaa"} -> {h: 1001, k: "fugafuga", v: "hh"} -> null 2: {h: 1106, k: "piyo", v: "zzz"} -> {h: 1106, k: "piyofuga", v: "abc"} -> {h: 18, k: "foo", v: "bar"} -> null 3: {h: 3, k: "moe", v: "ccc"} -> null ``` "hoge"のvalueを求める場合は、"hoge"のhashは`1000`ですので、`1000 % (4 - 1) = 0`(4はtabelのサイズ)を求めて、インデックスにある{h: 1000, k: "hoge", v: "fuga"}を得ます。そして、hashとkeyが同じであれば、そのvalueを採用します。もし、違っている場合は、次のエントリーを順番に辿ります。他のキーの場合も同様に行います。また、NodeではなくTreeNodeになっている場合があります。この場合は、二分木ですので、二分探索が行われます。どれも同じ物がなく`null`になったときは、エントリー無しとして`null`を返します。 一つ注意して欲しいのは、valueを確定するときは、hashとkeyの両方が同じかどうかを見ると言うことです。上の例では2のところにある二つのエントリーでhashが同じです(この実装ではhashが衝突しても**問題ありません**)。しかし、"piyofuga"を検索したときは、keyも比較するため、最初のエントリーは採用されず、二つ目のエントリーを返します。 さらに細かい動作(どういう風に配列を拡張するか、二分木はいつ使われるのか、二分木がどのように実装されているか)は実際のソースコードを確認してみて下さい。