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

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

ただいまの
回答率

90.34%

  • Java

    16757questions

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

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 1,304
退会済みユーザー

退会済みユーザー

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

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

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

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

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

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

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

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2016/08/19 21:32

    こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 3

checkベストアンサー

+1

具体的な実装を知りたければ、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におけるhashkeyvalueであり、->は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/21 12:30

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

    キャンセル

  • 2016/08/21 13:15 編集

    ハッシュテーブル実装中で二分探索のような木構造が登場することは、教科書的なハッシュ実装では必要としない「キーが比較可能(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 22:56

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

    キャンセル

0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/08/21 12:35

    返信ありがとうございます。
    色々調べたり、実装してみたりしてみたので、少しは理解できるようになったと思います。
    その上で以下のところの文意が読み取れませんでした。
    もう少しお付き合いいただければ、嬉しいです。

    「キー値とハッシュした値の長さが同じ場合」キー値とハッシュ値が一対一の対応と言われてますが、衝突は起こらないのでしょうか?
    ハッシの定義は値の長さが3であるとして、値100とハッシュ関数にかけると、200が返ってきて、値300をハッシュ関数にかけると、200が返ってくる。
    というようなものが自然だとは思うのですが、iwamoto_takaakiさんの意図はこれではないですよね?
    つまり、値100をハッシュ関数にかけて、100が返ってくるのであれば、一対一の対応になる、というようなものだと思うのですが、ハッシュ関数にそのような機能はあるのでしょうか?

    「逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。」
    ここから前提が変わっていますでしょうか?
    この文以前の話は配列があって、そのインデックスはキーをハッシュした値で中身はオブジェクト、というような状況だと思うのですが、ここから(この文の場合)配列が二つあって、その配列の中に配列かもしくはリストがある。
    ということでしょうか?
    次のこの文「多少、衝突があっても検索範囲が狭められる分、比較の量が減ります。」もそのように考えると理解できました。

    「実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。」
    ここから、再び配列とオブジェクトの一番簡単な実装のことを指していますでしょうか?



    キャンセル

  • 2016/08/21 14:34 編集

    あまり人に説明したことのない部分なので、自分でもいろいろ勉強になるなぁと思いながら回答しています。
    説明に苦労して、文章そのものも荒れてきて読みづらいことと思いますがよろしくお願いします。

    >「キー値とハッシュした値の長さが同じ場合」キー値とハッシュ値が一対一の対応と言われてますが、衝突は起こらないのでしょうか?

    そうですね、ハッシュ関数によってはあり得ると思います。
    ハッシュ関数に詳しくないのにいい加減な回答でした。

    > つまり、値100をハッシュ関数にかけて、100が返ってくるのであれば、一対一の対応になる、というようなものだと思うのですが、ハッシュ関数にそのような機能はあるのでしょうか?

    ハッシュの機能に一様性というものがあり、偏った入力値でもバラバラな値を返す性質です。一様性はハッシュ関数の機能として、必須の機能ではありませんがハッシュテーブルにとっては重要な機能です。

    一般的に用いられるハッシュ関数がどのようになっているかについては、私は知りません。

    しかし、理想的にはハッシュ長と同じキー長であれば衝突が起こらないものとなります。私は、ある種の乱数表のようなものを想像しています。ビットの入れ替えやxorで変換すれば、一対一にすることができます。

    >「逆にハッシュ値が1ビットでもあれば、比較の量は半分になります。」
    >ここから前提が変わっていますでしょうか?

    そうです。
    ハッシュの長さをキー長から1ビットに変えています。

    ハッシュ値の全検索を行う(つまり二分木を使わない)場合は、適切に衝突したほうが検索の件数が減ることを説明したくて書きました。

    >この文以前の話は配列があって、そのインデックスはキーをハッシュした値で中身はオブジェクト、というような状況だと思うのですが、ここから(この文の場合)配列が二つあって、その配列の中に配列かもしくはリストがある。
    ということでしょうか?

    そうです。
    二次元配列やジャグ配列やList<Pair<Hash,List<Pair<Key, Value>>>>です。

    >「実際には、ハッシュ値の衝突が起こった際のオブジェクトの保存方法に次のインデックス値に保存するなどの幾つかの方お方があるようです。」
    ここから、再び配列とオブジェクトの一番簡単な実装のことを指していますでしょうか?

    そうです。実装の話です。
    しかし、いまいち理解が浅い内容を書いてしまったと後悔してます。

    それに、「方お法」→「方法」です。プログラマらしからぬ間違いの多さに我ながら驚きます。

    キャンセル

  • 2016/08/21 22:56

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

    キャンセル

-1

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

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

二つ目の実装(二分探索木)に関しても、これはハッシュ関数を用いるのでしょうか。
使います。先の方法がハッシュ値が衝突しないように予めかなり大きくメモリを取るのに対し、平衡木を使うのはその場で衝突しないキーを探索するので省メモリで済みます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/08/19 23:15

    回答ありがとうございます。
    一つ目の方法(連結リストを用いる方)についてですが、次のような理解でよろしいでしょうか。


    配列が3つの要素を持つとします。
    そして、一つ一つの配列に連結リストがあり、それぞれの連結リストはオブジェクトとハッシュ値の組み合わせである。

    二つめの二分検索木に関してですが、キーのハッシュ値により二分検索木を形成しているということですね?
    ハッシュ値は重複は許されませんから、その意味では一つめの方法と違いがないように思えます。
    「その場で衝突しないキーを探索する」とは一体どういう意味なのでしょうか。

    キャンセル

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

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Java

    16757questions

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