ハッシュテーブルの実装についての質問になります。
私の使っている本のハッシュテーブルのところで次のような記述がありました。
「ハッシュテーブルは非常に効率的な検索を行うために、キーを値にマップするデータ構造です。ハッシュテーブルのごく単純な実装には元になる配列とハッシュ関数を用います。オブジェクトとキーを挿入した時、ハッシュ関数はキーを整数値にマッピングし、それは」配列のインデックスを示します。そしてオブジェクトには、そのインデックスに保存されます。
ですが、これは一般的には正しく動作しません。上記の実装では、すべてのキーに対するハッシュ値は一意でなければなりません。そうでなければ誤って配列上のデータを書き換えてしまうかもしれないからです。そのような「衝突」を避けるためには配列は非常に大きなサイズ、それも存在しうるすべてのキーのサイズほどのものを用意しなければなりません。
巨大な配列を作り、キーのハッシュ値をそのままインデックスとする代わりに、ずっと小さなサイズの配列と、ハッシュ値を配列サイズで割った余りをインデックスとした連結リストに保存する方法があります。特定のキーからオブジェクトを得るには対応する連結リストからキーを探索します。
あるいは、二分探索木を使ってハッシュテーブルを実装することもできます。二分探索木の平衡を保つことで、O(log(n))の探索時間を保証することができます。さらに言えば、最初に大きな配列を割り当てる必要も無くなるので、省メモリにもなります。」
後半の二つの実装がよくわかりません。
何がどうなっているのでしょうか。
一つ目の実装(小さなサイズの配列と連結リスト)の場合、オブジェクトはどこにあるのか、キーはどこにあるのか等がよくイメージできません。
二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。
理解できた方、回答お願いします。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答3件
0
ベストアンサー
具体的な実装を知りたければ、OpenJDK8 java.util.HashMapのソースを見るのが良いかと思います。OpenJDKでは配列のインデックスと二分探索のハイブリッドな実装のようです。以下、適当に解説します(さらっとしか見てませんので、間違いがあるかも知れません)。
各エントリーはNode<K, V>
のオブジェクトとして扱われます。これは、key
とvalue
の他に計算済みのhash
が含まれます。hash
はkey.hashcode()
から求められます。そして、もう一つ重要なことにNode<K, V>
にはnext
があり、片方向連結リストとして構成されるようになっています。さらにTreeNode<K, V>
も用意されています。これはそのまま二分木になるように構成されています。
さて、HashMap<K, V>
で実際のエントリーが保存されているのは、Node<K,V>[]
型の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も比較するため、最初のエントリーは採用されず、二つ目のエントリーを返します。
さらに細かい動作(どういう風に配列を拡張するか、二分木はいつ使われるのか、二分木がどのように実装されているか)は実際のソースコードを確認してみて下さい。
投稿2016/08/19 19:16
編集2016/08/19 19:23総合スコア21733
0
確かに、うまく衝突が起こった際にうまくいきそうにないですね。
”ハッシュ 衝突”または、”ハッシュ コリジョン”で検索すると求めている回答が書いてあるかと思いますが、説明に挑戦してみようと思います。(他の回答者の方、間違いの指摘歓迎します)
ハッシュのキー値が衝突しない方法が1つだけあります。
キー値とハッシュした値の長さが同じ場合です。または、ハッシュ関数を使わずキーをそのまま保存する方法です。
キーとハッシュが必ず1対1になるなら衝突はありえません。
しかしこれは、衝突こそ避けられたものの1つずつ比較するので、全検索となり非効率です。また、ハッシュ値の計算の分も非効率です。逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。
多少、衝突があっても検索範囲が狭められる分、比較の量が減ります。実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。
取り敢えずは、ハッシュ値をインデックスに使って、複数のキーと値(オブジェクト)のペアが取得出来るのがハッシュテーブルで、複数あるキーから求めているキーを持つ値を取得しているというのがざっとしたデータ構造です。
ここまでがハッシュ値に関する説明です。本で説明したかった点は、同じハッシュ値で複数値を持てるようにして、キーの比較の量(O(√n)かな)を減らしている点だと思います。
更に進めて、ハッシュ値からキー(群)を素早く検索する方法が二分木の方法です。ハッシュとは直接関係はなく、リスト上の値を素早く検索するためのアルゴリズムです。
この説明も端折って説明しますが、このような二分木を作るとハッシュ値の検索がやはり減ります。これは、かなり強引な説明になりますが、インデックスのインデックスをつかっていると考えて下さい。(詳しくは、アルゴリズムとデータ構造について、調べてみてください。)
この方法の良い所は、ハッシュ値どおしの比較の回数が格段に減るので、ハッシュ値の長さが検索時間に与える影響を軽減するとこが出来ます。
ということで、二分木を使ったハッシュテーブルは衝突がちょうど起こらないかそれより長いくらいのハッシュ値の長さが良いことになりそうです。
ここまでが、説明です。
私の説明がうまくできていれば、キー値で二分木を作っても良いのではという疑問がでるかと思います。(笑)
二分木について調べるとわかるのですが、近い値・連続した値など偏りがある登録に二分木は弱く結局、全検索に近くなる場合があります。とくに、電話番号などをキーにすると偏りが起こりやすいのでキーが近くてもテンでバラバラな値を返す関数を使い偏りをなくします。これをハッシュ関数と呼びます。
これが、ハッシュを二分木で使う理由です。
投稿2016/08/19 14:29
総合スコア2883
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2016/08/20 06:18
退会済みユーザー
2016/08/21 03:35
2016/08/21 05:36 編集
退会済みユーザー
2016/08/21 13:56
0
オブジェクトがどこにあるのかを知るためのキーです。
キーがどこに有るかわからないというのは文字通り鍵をなくしたことになるのでちゃんと自分で管理してください。
でもキーがたくさんあると管理が煩雑になりますよね。なのでキーを整数で割った余りをグループ番号としてグループ管理するんです。これで番号さえ知っていればグループの中から鍵を探せば良いのでよっぽど管理が楽になります。
二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。
使います。先の方法がハッシュ値が衝突しないように予めかなり大きくメモリを取るのに対し、平衡木を使うのはその場で衝突しないキーを探索するので省メモリで済みます。
投稿2016/08/19 13:23
総合スコア910
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/08/19 14:15
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/08/20 03:15
2016/08/20 03:39
退会済みユーザー
2016/08/21 03:20
2016/08/21 03:30
2016/08/21 04:16 編集
退会済みユーザー
2016/08/21 13:56