質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

3回答

3328閲覧

ハッシュテーブルについて

退会済みユーザー

退会済みユーザー

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2016/08/19 12:03

ハッシュテーブルの実装についての質問になります。

私の使っている本のハッシュテーブルのところで次のような記述がありました。
「ハッシュテーブルは非常に効率的な検索を行うために、キーを値にマップするデータ構造です。ハッシュテーブルのごく単純な実装には元になる配列とハッシュ関数を用います。オブジェクトとキーを挿入した時、ハッシュ関数はキーを整数値にマッピングし、それは」配列のインデックスを示します。そしてオブジェクトには、そのインデックスに保存されます。

ですが、これは一般的には正しく動作しません。上記の実装では、すべてのキーに対するハッシュ値は一意でなければなりません。そうでなければ誤って配列上のデータを書き換えてしまうかもしれないからです。そのような「衝突」を避けるためには配列は非常に大きなサイズ、それも存在しうるすべてのキーのサイズほどのものを用意しなければなりません。

巨大な配列を作り、キーのハッシュ値をそのままインデックスとする代わりに、ずっと小さなサイズの配列と、ハッシュ値を配列サイズで割った余りをインデックスとした連結リストに保存する方法があります。特定のキーからオブジェクトを得るには対応する連結リストからキーを探索します。

あるいは、二分探索木を使ってハッシュテーブルを実装することもできます。二分探索木の平衡を保つことで、O(log(n))の探索時間を保証することができます。さらに言えば、最初に大きな配列を割り当てる必要も無くなるので、省メモリにもなります。」

後半の二つの実装がよくわかりません。
何がどうなっているのでしょうか。
一つ目の実装(小さなサイズの配列と連結リスト)の場合、オブジェクトはどこにあるのか、キーはどこにあるのか等がよくイメージできません。

二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。

理解できた方、回答お願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

具体的な実装を知りたければ、OpenJDK8 java.util.HashMapのソースを見るのが良いかと思います。OpenJDKでは配列のインデックスと二分探索のハイブリッドな実装のようです。以下、適当に解説します(さらっとしか見てませんので、間違いがあるかも知れません)。

各エントリーはNode<K, V>のオブジェクトとして扱われます。これは、keyvalueの他に計算済みのhashが含まれます。hashkey.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
raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/20 03:15

非常にわかりやすかったです。 本当にありがとうございます。 二分探索木の場合は、この場合も連結リストと同様に配列があって、その中の要素としてTreeNodeがあるのかなと思ったのですが、どうでしょうか? そして、連結リストよりも高速で検索が可能になると思いました。
raccy

2016/08/20 03:39

実装上は連結リストと二分木を区別なく扱っています。連結するエントリー数が多くなる(定数TREEIFY_THRESHOLD以上)と二分木へ切り替わるようにしています(643行目あたり)。ですので、tableの配列には連結リストと二分木がごっちゃまぜになっている場合もあり得るようです。 エントリーが少ないときは単純な配列や連結リストで一つあたりの処理を軽くし(O(n)だがnが十分小さければこっちの方が速い)、エントリーが多いときは二分木に切り替えて高速に検索できるようにする(O(log n)になるため、数が多くなっても全体処理速度があまり落ちない)という工夫がされているようです。
退会済みユーザー

退会済みユーザー

2016/08/21 03:20

回答ありがとうございます。 HashMapでは例えば、要素を削除するとき、まずハッシュ値を比較して、同じだった場合に、equalsメソッドで確認し、その結果がtrueだった場合に削除するそうです。 そうすると、二分木の場合、keyではなく、ハッシュ値で並んでいるイメージでしょうか? つまり、ノードを挿入するときに、ハッシュ値の値でどこに挿入されるか決まると私は考えているのですが、この認識でよろしいでしょうか?
raccy

2016/08/21 03:30

その通りです。最初のtableも二分木も全てhashで管理して、hashの順番で並べています。hashは整数(int)のため比較や計算が高速であり、まずは全てhashで確認するようにしています。hashが同じ場合のみ、keyも本当に同じかどうかを確認(この処理は低速)するという動作です。keyは最終確認のみで、それまではhashで高速にするというのがハッシュテーブルが高速である仕組みです。
yohhoy

2016/08/21 04:16 編集

ハッシュテーブル実装中で二分探索のような木構造が登場することは、教科書的なハッシュ実装では必要としない「キーが比較可能(Comparable)であること」要求するため強い違和感があったのですが、この挙動はJava8で追加拡張された仕様なのですね... 勉強になりました。 http://interprism.hatenablog.com/entry/2014/04/04/125444 http://coding-geek.com/how-does-a-hashmap-work-in-java/
退会済みユーザー

退会済みユーザー

2016/08/21 13:56

回答ありがとうございました。
guest

0

確かに、うまく衝突が起こった際にうまくいきそうにないですね。

”ハッシュ 衝突”または、”ハッシュ コリジョン”で検索すると求めている回答が書いてあるかと思いますが、説明に挑戦してみようと思います。(他の回答者の方、間違いの指摘歓迎します)

ハッシュのキー値が衝突しない方法が1つだけあります。
キー値とハッシュした値の長さが同じ場合です。または、ハッシュ関数を使わずキーをそのまま保存する方法です。

キーとハッシュが必ず1対1になるなら衝突はありえません。

しかしこれは、衝突こそ避けられたものの1つずつ比較するので、全検索となり非効率です。また、ハッシュ値の計算の分も非効率です。逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。

多少、衝突があっても検索範囲が狭められる分、比較の量が減ります。実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。

取り敢えずは、ハッシュ値をインデックスに使って、複数のキーと値(オブジェクト)のペアが取得出来るのがハッシュテーブルで、複数あるキーから求めているキーを持つ値を取得しているというのがざっとしたデータ構造です。

ここまでがハッシュ値に関する説明です。本で説明したかった点は、同じハッシュ値で複数値を持てるようにして、キーの比較の量(O(√n)かな)を減らしている点だと思います。

更に進めて、ハッシュ値からキー(群)を素早く検索する方法が二分木の方法です。ハッシュとは直接関係はなく、リスト上の値を素早く検索するためのアルゴリズムです。

この説明も端折って説明しますが、このような二分木を作るとハッシュ値の検索がやはり減ります。これは、かなり強引な説明になりますが、インデックスのインデックスをつかっていると考えて下さい。(詳しくは、アルゴリズムとデータ構造について、調べてみてください。)

この方法の良い所は、ハッシュ値どおしの比較の回数が格段に減るので、ハッシュ値の長さが検索時間に与える影響を軽減するとこが出来ます。

ということで、二分木を使ったハッシュテーブルは衝突がちょうど起こらないかそれより長いくらいのハッシュ値の長さが良いことになりそうです。

ここまでが、説明です。
私の説明がうまくできていれば、キー値で二分木を作っても良いのではという疑問がでるかと思います。(笑)

二分木について調べるとわかるのですが、近い値・連続した値など偏りがある登録に二分木は弱く結局、全検索に近くなる場合があります。とくに、電話番号などをキーにすると偏りが起こりやすいのでキーが近くてもテンでバラバラな値を返す関数を使い偏りをなくします。これをハッシュ関数と呼びます。

これが、ハッシュを二分木で使う理由です。

投稿2016/08/19 14:29

iwamoto_takaaki

総合スコア2883

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/20 02:59

回答ありがとうございます。 ハッシュコリジョンで検索してみましたが、あまりわかりませんでした。orz 回答をじっくりと読ませていただいたのですが、いまいちわからないところが多々ありました。 お答え頂ければ幸いです。 「キー値とハッシュした値の長さが同じ場合です。または、ハッシュ関数を使わずキーをそのまま保存する方法です。」 ひょっとして、キー値というのは値を想定していますか? そして、キー値とハッシュ関数により得られる値の長さが同じ場合、そのキーを直接保存するというのが、iwamoto_takaakiさんの意図でしょうか。 私はてっきり、キーというのはもっと一般的なもので、インスタンス等も良いと考えいて、変数.hashCode()でハッシュ値を得ると思っているのですが。。 「本で説明したかった点は、同じハッシュ値で複数値を持てるようにして、キーの比較の量(O(√n)かな)を減らしている点」 これは一つめの実装(連結リスト)のことを言っていると思うのですが、例えば100個のキーと値のペアがあったとします。 これらのキーのハッシュ値を5で割り、その余りからどの配列に配置するかを決めます。 実際には配列の中には連結リストが入っていて、その連結リストにハッシュ値とオブジェクトの形で格納されているのでしょうか?
iwamoto_takaaki

2016/08/20 06:18

長い文章で内容も難しかったので、読んでもらえて嬉しいです。 >ひょっとして、キー値というのは値を想定していますか? はい。 文字列であってもバイトの列です。比較できる何らかの変数はバイトの列の比較とみなすことが来ます。またそのほうが都合が良いのです。というのも、ハッシュ関数や二分検索木のアルゴリズムのところで は、値として扱っているからです。 >私はてっきり、キーというのはもっと一般的なもので、インスタンス等も良いと考えいて、変数.hashCode()でハッシュ値を得ると思っているのですが。。 hashCode()も衝突を起こすようです。Oracleのドキュメントを調べて見たらこのような記述がありました。 http://docs.oracle.com/javase/jp/7/api/java/lang/Object.html#hashCode() >クラス Object によって定義された hashCode メソッドは、可能なかぎり、異なるオブジェクトに対して異なる整数を返します。 "可能な限り"と言うのは、衝突があり得ることを暗に示しています。また、equals()の実装に合わせる指定もあります。(実際には極々少ない可能性なのでテストデータでエラーになることはほぼありえませんが、例えば自身でハッシュテーブルを実装する際には、ハッシュで検査した後に必ずequalsで再検査する必要があると思います。) >equals(Object) メソッドに従って 2 つのオブジェクトが等しい場合は、2 つの各オブジェクトに対する hashCode メソッドの呼び出しによって同じ整数の結果が生成される必要があります。 つまり、 "a b".split(' ')[0].hashCode() == "a".hashCode() はTrueになる必要があるということです。(別々にインスタンスを作られた文字列"a"はequalsでの比較結果も、hashCodeの比較結果も同じになる。)この場合のキーは文字列”a”となります。 つまり、Javaの言語仕様レベルでも、(ガイドラインとして)オブジェクト毎に適切なキーを作ることが推奨されているということです。 >これは一つめの実装(連結リスト)のことを言っていると思うのですが、例えば100個のキーと値のペアがあったとします。 >これらのキーのハッシュ値を5で割り、その余りからどの配列に配置するかを決めます。 >実際には配列の中には連結リストが入っていて、その連結リストにハッシュ値とオブジェクトの形で格納されているのでしょうか? 架空すべき値が100と決まっているなら、ハッシュは100のルートを取って、10の余剰にするべきです。10個のハッシュ値から、絞られた10個前後のキーと値のペアから比較すると比較の回数の期待値が一番少なくなるからです。(O(√n)の根拠) データの構造としてはこんな感じでしょうか。 [hashCode, [key, object]] ハッシュ毎に、キーとオブジェクトの配列を持っていることにします。 連結リストで作る際には、ハッシュ毎に100個のキーとオブジェクトからなる配列を持つことが無難です。 こういったものは、どちらかと言うとご自身で実装してみるのが一番の勉強になります。ここまで踏み込んで勉強したのですからすごく良い経験になると思います。 また、別の視点では今読んでいる本が、薄すぎるのかもしれいないなと思います。コードがどんどん書いてあって分厚くなった本の方がbillさんにはあっているかもしれません。
退会済みユーザー

退会済みユーザー

2016/08/21 03:35

返信ありがとうございます。 色々調べたり、実装してみたりしてみたので、少しは理解できるようになったと思います。 その上で以下のところの文意が読み取れませんでした。 もう少しお付き合いいただければ、嬉しいです。 「キー値とハッシュした値の長さが同じ場合」キー値とハッシュ値が一対一の対応と言われてますが、衝突は起こらないのでしょうか? ハッシの定義は値の長さが3であるとして、値100とハッシュ関数にかけると、200が返ってきて、値300をハッシュ関数にかけると、200が返ってくる。 というようなものが自然だとは思うのですが、iwamoto_takaakiさんの意図はこれではないですよね? つまり、値100をハッシュ関数にかけて、100が返ってくるのであれば、一対一の対応になる、というようなものだと思うのですが、ハッシュ関数にそのような機能はあるのでしょうか? 「逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。」 ここから前提が変わっていますでしょうか? この文以前の話は配列があって、そのインデックスはキーをハッシュした値で中身はオブジェクト、というような状況だと思うのですが、ここから(この文の場合)配列が二つあって、その配列の中に配列かもしくはリストがある。 ということでしょうか? 次のこの文「多少、衝突があっても検索範囲が狭められる分、比較の量が減ります。」もそのように考えると理解できました。 「実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。」 ここから、再び配列とオブジェクトの一番簡単な実装のことを指していますでしょうか?
iwamoto_takaaki

2016/08/21 05:36 編集

あまり人に説明したことのない部分なので、自分でもいろいろ勉強になるなぁと思いながら回答しています。 説明に苦労して、文章そのものも荒れてきて読みづらいことと思いますがよろしくお願いします。 >「キー値とハッシュした値の長さが同じ場合」キー値とハッシュ値が一対一の対応と言われてますが、衝突は起こらないのでしょうか? そうですね、ハッシュ関数によってはあり得ると思います。 ハッシュ関数に詳しくないのにいい加減な回答でした。 > つまり、値100をハッシュ関数にかけて、100が返ってくるのであれば、一対一の対応になる、というようなものだと思うのですが、ハッシュ関数にそのような機能はあるのでしょうか? ハッシュの機能に一様性というものがあり、偏った入力値でもバラバラな値を返す性質です。一様性はハッシュ関数の機能として、必須の機能ではありませんがハッシュテーブルにとっては重要な機能です。 一般的に用いられるハッシュ関数がどのようになっているかについては、私は知りません。 しかし、理想的にはハッシュ長と同じキー長であれば衝突が起こらないものとなります。私は、ある種の乱数表のようなものを想像しています。ビットの入れ替えやxorで変換すれば、一対一にすることができます。 >「逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。」 >ここから前提が変わっていますでしょうか? そうです。 ハッシュの長さをキー長から1ビットに変えています。 ハッシュ値の全検索を行う(つまり二分木を使わない)場合は、適切に衝突したほうが検索の件数が減ることを説明したくて書きました。 >この文以前の話は配列があって、そのインデックスはキーをハッシュした値で中身はオブジェクト、というような状況だと思うのですが、ここから(この文の場合)配列が二つあって、その配列の中に配列かもしくはリストがある。 ということでしょうか? そうです。 二次元配列やジャグ配列やList<Pair<Hash,List<Pair<Key, Value>>>>です。 >「実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。」 ここから、再び配列とオブジェクトの一番簡単な実装のことを指していますでしょうか? そうです。実装の話です。 しかし、いまいち理解が浅い内容を書いてしまったと後悔してます。 それに、「方お法」→「方法」です。プログラマらしからぬ間違いの多さに我ながら驚きます。
退会済みユーザー

退会済みユーザー

2016/08/21 13:56

丁寧な回答本当にありがとうございました。
guest

0

オブジェクトがどこにあるのかを知るためのキーです。
キーがどこに有るかわからないというのは文字通り鍵をなくしたことになるのでちゃんと自分で管理してください。

でもキーがたくさんあると管理が煩雑になりますよね。なのでキーを整数で割った余りをグループ番号としてグループ管理するんです。これで番号さえ知っていればグループの中から鍵を探せば良いのでよっぽど管理が楽になります。

二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。

使います。先の方法がハッシュ値が衝突しないように予めかなり大きくメモリを取るのに対し、平衡木を使うのはその場で衝突しないキーを探索するので省メモリで済みます。

投稿2016/08/19 13:23

nullbot

総合スコア910

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/19 14:15

回答ありがとうございます。 一つ目の方法(連結リストを用いる方)についてですが、次のような理解でよろしいでしょうか。 配列が3つの要素を持つとします。 そして、一つ一つの配列に連結リストがあり、それぞれの連結リストはオブジェクトとハッシュ値の組み合わせである。 二つめの二分検索木に関してですが、キーのハッシュ値により二分検索木を形成しているということですね? ハッシュ値は重複は許されませんから、その意味では一つめの方法と違いがないように思えます。 「その場で衝突しないキーを探索する」とは一体どういう意味なのでしょうか。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問