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

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

ただいまの
回答率

88.10%

ハッシュ探索とは、データをハッシュ値で出力してその値で直接アクセスして探索するということ?

受付中

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 3,911

score 162

データの探索アルゴリズムの一つに「ハッシュ法」という手法がありますが、
このハッシュ(探索)法とは
私自身の解釈として、(おおまかでありますが、)

  1. 探索したいデータをハッシュ関数で計算する

  2. ハッシュ値(キー値。アドレスみたなもの?)を出力する。

  3. 出力したハッシュ値を元に、データ列にあるハッシュ表から直接該当するハッシュ値(キー値)にアクセス(探索)する。

このような感じであると私自身思いますが、つまり、「ハッシュ探索法」は

「出力したハッシュ値を元にデータ列にあるハッシュ表から直接アクセスしてデータを探索する」

ということなんでしょうか?(大雑把ですが・・・)

何か所々解釈が間違っていると思いますが、その解釈でいいのでしょうか?

よろしくお願いします。

(ちなみに掲載されている図はあくまで例であることを御了承いただけばと思います。)

ハッシュ値とデータを紐付けして格納

ハッシュ値を元に該当するデータを探索

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 4

+2

抽象的な記述なので、なんとも言いがたいですが、おそらく間違っています。

データを格納するテーブルサイズをNとすると、データ中のキーとなる値(質問の例だと果物名)のハッシュ値を求め、その値に何らかの演算を行って0N-1の添え字を求めます。

テーブルのその添え字の場所に、データを格納します。実際は、データへのポインタを格納すると思いますが。
当然、異なるキー値に対して、添え字の重複が発生します。重複した場合(=求めた添え字の場所に既にデータが格納済みである場合)は、その近くの添え字の場所にデータを格納したり、添え字の場所から、線形リストで、同じ添え字になったデータをつなげたりします。

参照の場合は、求めた添え字の場所のキー値が等しければそれ。異なれば近くを探すか、リストをたどります。

データが増えてテーブルサイズがNで足りなくなった場合は、テーブルの拡張が必要です。そのあたりを実装したことないですが、おそらく、ハッシュ値から添え字を求め直して、データ(のポインタ)を移動させるんじゃないでしょうか。移動しないで済む方法もありそうな気もしますが。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2019/04/27 20:55

    > サイズ2倍のテーブルを作成しハッシュ値を再計算して格納
    拡張とは言うものの、再作成ですね。
    あ、ハッシュ値の作成もなるべく均一になるようすべきなので、そこも腕の見せ所でしたね。(難しいですが)

    キャンセル

  • 2019/04/28 01:26

    > 質問の説明と書き方の違いだけで、同じように感じるのですが。
    質問文では、テーブルの絵が間違っていますね。
    絵が無くて文章だけなら、合っているか間違っているか「微妙」というところです。

    キャンセル

  • 2019/04/28 01:48

    > 「テーブルの拡張」はあるのでしょうか? 拡張でなく、再作成ではないでしょうか?
    再作成は、拡張の一手段です。回答にに書いたとおりで、おそらく再作成だが、もしかすると再作成でない拡張もあるかも知れないので、そういう記述にしました。

    > 元々のデータをそのまま、キーにすると、テーブルサイズが大きくなるので、ハッシュテーブルで、テーブルサイズを小さくし、検索を容易にするのでは無かったですか?

    この表現も微妙ですね。キーにするというかテーブルの添え字にするので、元々のデータが整数値でないと添え字に出来ません。
    正しく書き直すと、
    「元々のキーでは、テーブルの添え字に出来ないか出来ても膨大なサイズのテーブルになるので、ハッシュ計算により実用的な範囲の整数に直してテーブルの添え字にする」
    でしょう。

    キャンセル

+2

大体あっていると思いますよ。
ただし、現実にはデータと数値を完全に1対1に対応付けるのが不可能なので、同じハッシュの結果になったものはリストなどの形で同じ場所に収められる、などの形態がとられているくらいでしょうか。単に全部をリストにするとすべてのデータを探さなければいけないのに対し、同じデータである可能性のある一部のデータだけ探せば済みます。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

+2

他の回答者も書いていますが「ハッシュ関数」の衝突を補足します。

ハッシュ関数の出力は衝突する  

『世界標準MIT教科書 Python言語によるプログラミングイントロダクション第2版』近代科学社より引用。

『ハッシュ関数は大きな集合から小さな集合への写像である。ハッシュ関数を用いることで、大きな集合の属するキーを小さな集合に属する整数へと変換できる。ハッシュ関数の出力の集合は入力の集合に比べて小さいため、ハッシュ関数は、多対1写像 (many-to-one mapping) を生成する。2つの入力が同一の出力へ写像される場合を衝突 (collision) という。衝突がなるべく起きないようにするには、各出力が均等に発生するような一様分布 (uniform distribution) を作り出すハッシュ関数を考案しなければならない。』

  • ハッシュ関数は、多対1写像 (many-to-one mapping) 
    ミカンとリンゴを入力とすると、同じ値が出力されることがある。
  • 2つの入力が同一の出力へ写像される場合を衝突 (collision) という。
    一つの指定席に二人(以上)の人が座りたいということが起る。衝突をできるだけ回避するために出力を一様分布にしたい。

ハッシュテーブルの実装

衝突を考えると、配列に格納するために工夫が必要になります。

  • 同じハッシュ値のエントリを隣に置く
    本来隣は別のハッシュ値の指定席なので、どんどんずれる。空席に出会うまで衝突かどうか線形探索する必要がある。
  • 指定席自体を配列や連結リストにして衝突を格納できる構造にする。
    質問の図のような単純な配列ではなく、配列の配列や、結合リストの配列にする。

入力のビットの数を数えて偶数なら0奇数なら1というハッシュ関数をつくると出力値は2つ。大量の衝突が起きる。衝突の中からめざす値(リンゴかミカンか、...)を発見するのにリストをさらに線形探索する。このようにハッシュ関数が悪いと非効率。

ハッシュ関数の実装 

上の本にはハッシュ関数の実装について書かれていません。以下の本を読んでください。
『世界標準MIT教科書 アルゴリズムインロダクション第3版 第1巻』近代科学社
衝突の起きるハッシュ関数だけでなく、衝突の起きない「完全ハッシュ法」も紹介されています。

ハッシュ関数の応用 

パスワード、電子署名など様々な分野で使われています。wikipediaを読んでみましょう。

【追記(2019-04-28)】

キーと値  

ハッシュ値(配列の添字)が「キー」と思われているようですが間違いです。キーは「リンゴ」「ミカン」になります。英語の辞書に例えると、英単語が「キー」単語の説明が「値」に相当します。質問の例は「キー」と「値」が同じ辞書です。ハッシュテーブルを「辞書」「連想配列」「ハッシュ」と呼ぶことがあります。

ハッシュテーブルのエントリ  

通常は(キー、値)のペアになります。理由は、衝突リストに格納されたエントリを識別するのにキーの同値判定が必要だから。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

-1

実装とかはotnさんの回答されいてるようなことだと思いますが…

キーが付与されていない大きめのデータを効率よく探索したい
てのが要点なんじゃないかなあ。
例示されたような小さいものだとハッシュ値がかぶりまくりで
うまく運用するのは難しいと思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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