ハッシュ探索とは?

このQ&Aのポイント
  • ハッシュ探索はデータをハッシュ値に変換して比較に用いる方法です。
  • ハッシュ値の長さによって処理時間が変化することもあります。
  • ハッシュ探索は文字列の長さに応じて処理時間が変わることがあります。
回答を見る
  • ベストアンサー

ハッシュ探索とはどういうイメージなのか?

ハッシュ探索というのは「対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式」ということですが、どういうものなのかイメージが思いつきません。 これはつまり、データ本体を「ハッシュ」という文字列に変換して、ハッシュ値として出力したものを、比較する(全ての文字列において比較する)というイメージでよいのでしょうか? もしそうだとしたら、ハッシュ値の長さ(文字列の長さ)に応じて(比較)処理時間が変わってくるのでしょうか? 例えば、(あくまで例です。) 6文字程度のハッシュ値→0.2秒で(比較処理時間が)終わる 3万文字程度のハッシュ値→3秒ぐらい(比較処理時間が)かかる ↑こういう風にハッシュ探索は文字列の長さに応じて処理時間が変化するのでしょうか? 回答のほうお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • notnot
  • ベストアンサー率47% (4834/10234)
回答No.1

ハッシュ化と言うのは、いろいろな文字列やバイト列を、固定長のできるだけ重複しない(他と同じにならない)データに変換することです。 元のデータの長さによってハッシュ化の時間が変わるかというと、それは全く同じというわけには行きません。長さに比例して10ナノ秒だったり1ミリ秒だったりするかと思います。 ハッシュ探索はハッシュ値を使った探索(配列から目的のデータを探す)なので、すでにハッシュ化されたデータを使いますから、もとのデータの長さとは関係ありません。

その他の回答 (1)

  • asciiz
  • ベストアンサー率70% (6582/9329)
回答No.2

まず、ハッシュ化・ハッシュ関数の話から。 ハッシュ化とは、変換前の任意長のデータを、短い別データに変換することを指します。 例えば、元が100文字であっても、3万文字であっても、ハッシュ関数を通すと、16バイトのハッシュ値が計算される、と言った風にです。 大きいデータに演算を施して、小さなデータにしてしまいますから、中には、「元が違う文字列なのにハッシュ値が同じ」というパターンも存在し得ます。 しかしそこは計算方法の工夫により、そのようなことが起こる確率は非常に低くなっており、大概の場合には「ハッシュ値が一致したならば、元の文字列同士も一致している」と言えるんです。 ではここで例えば、100KBのデータをダウンロードしたとしましょう。 ダウンロードしたデータが正しいことをどうやって確認したら良いでしょうか? もう一度ダウンロードして、ファイル比較するという手段があります。 でもダウンロード元に、「MD5: 112233445566778899aabbccddeeff00」みたいなハッシュ値が書いてあれば、ダウンロードしたファイルをMD5方式でハッシュ値に変換し、同じ値に変換されれば、「正しくダウンロードできた」と信用できます。 なお、ハッシュ値による比較では、「一致しているかどうか」しか調べられません。 元の文字列が1文字違う、あるいは元の文字列が1文字長い、と言ったパターンから、かなり違うハッシュ値が算出されます。 ハッシュ値からは元の文字列を類推できないので、どちらが長かったか、すら分からないんです。 ---- 「ハッシュ探索」という言葉はどういう文脈で出てきたんでしょうね? 例えばウイルス対策ソフトとかでしょうか。 この場合、「既知のウイルスファイルであるか」を調べるのに、このハッシュ値を使います。 もし、ウイルスプログラムそのもののデータを持っていたら、チェック用データはどんどん大きくなりますし、そのデータからうまく切り出したらウイルスファイルを復元できることになってしまって危険極まりありません。 そこで、たくさんあるウイルスプログラムのハッシュ値を計算し、そのハッシュ値のみをデータベース化しておきます。 そして新しいプログラムがインストールされたとき、各ファイルのハッシュ値を計算してみます。 もし、その中に既存のハッシュ値と一致するものがあれば、「このプログラムはウイルスファイルを含んでいる!」と検出できたりするわけです。

関連するQ&A

  • ハッシュについて

    今、CGI作りに挑戦しているものです。 $data{a0} = "文字列"; とハッシュに「文字列」を入れて、 $sign = '0'; print "$data{a$sign}"; とやって、 「文字列」を表示させようとしたのですが、 Can't call method "a" without a package or object reference at test.cgi line *. と表示されて、「文字列」を表示できません。 ご教授いただけますようお願いします。

    • ベストアンサー
    • Perl
  • ハッシュ法でのデータ管理について教えてください

    ハッシュ法でのデータ管理をするプログラムを作りたいんですが長いことPASCALに触ってなかったせいか全く分かりません。 どなたか教えていただけないでしょうか??問題の概要は以下のようなものです。 表に登録するデータについては、キーは英数字からなる長さ8までの文字列でデータ本体は整数(型名はintegerでよい)です。 ハッシュ表のサイズは11とします。 ハッシュ関数は文字列xの各文字のASCIIコードの総和を11で割った余りとします。 さらにメニュー表示として入力した文字により行う操作を決定します。 どの文字がどのような操作を行うのかは以下のとおりです。 's' の場合: ハッシュ表に登録されている全レコードを,ハッシュ関数値毎に(キーの値とデータの両方を)すべて表示します. 'r' の場合: さらに「キーの値」と「データ」を入力し,すでに同じキーをもつデータがあれば「二重登録」として検出し,そうでなければ,そのレコードをハッシュ表に登録します. 'e' の場合: さらに「キーの値」を入力し,そのキーをもつデータがハッシュ表に登録されているならば, そのデータを表示します.さらに削除するかどうかを入力させて,削除する選択をした場合にはそのレ コードを削除します.そのキーをもつデータがハッシュ表にない場合には「そのキーをもつレコードが ないこと」を出力しますが,ハッシュ表には操作を加えません. 'i' の場合: ハッシュ表に登録されている全レコードを,キーの値が小さい順に表示します.ここで「キー の値の順」とは,文字列の辞書順のことを意味します.Pascal では,文字列a,b に対して,a がb より 辞書的順序が先(小さい) ときには「a<b」で表現できます. 'd' の場合: 「'i' の場合」の逆で,キーの値が大きい順に表示します. 'q' の場合: プログラムを終了します.具体的には,実行文部の最後の「end.」の直前までジャンプし ます. 長くなってすいません。ちょっとしたヒントでもいいので教えていただければ幸いです。

  • ハッシュテーブルを使って効率の良い文字の置換がしたい場合

    はじめまして。 実はいまハッシュテーブルを利用して複数の外字をそれぞれ対応する文字に変換するJavaのプログラムを考えています。 ただ、その方針までは決まったのですが、実装方法で躓いています。 今のところ、文字列をIndexOfで探して、ある外字がでてきたらハッシュテーブルを見にいってその外字に対応する文字に変換し、また続けてその文字を探していくという方式しか考え付いてないのですが、この方法だと外字一種類ごとに文字列を検索することになってしまい、不幸率のような気がしてきました。なにか他にもっといい方法はあるでしょうか?

    • ベストアンサー
    • Java
  • ハッシュについて教えて下さい

    現在出来るだけ高速に大量の英単語の登録(検索)を行いたいと考えています。 現在は受け付ける文字の種類を進数にして桁上げして、クローズドで(最初にがっぽり配列を用意してその中のどこかに入れる形式で)計算しています。 例えば0~9の文字のみ受け付ける仕様だとすると、文字の種類は10種類なので、「192」という文字列なら、 1*10^2 + 9*10^1 + 2*10^0 = 192番地に登録 といった感じです。今回大小アルファベットを含むので10→62で計算しています。 しかしこの方法では、62進数が膨大な数になるため、配列に上限があることから、完全なユニークな数値が生成出来ません。 ある程度ハッシュ値がぶつかってしまいます。 完全にユニークな数値は無理でしょうが、出来るだけ衝突は避けたいと考えています。 そこで、もっと効率よいハッシュ値を求めるMurMurHash 2.0というアルゴリズムを聞いたのですが、HPを見ても何が何だかよくわかりません; HPにてMurmurHash2.cppが公開されているので、もしご存知の方がいらっしゃればそのアルゴリズムを教えていただけないでしょうか。 http://www.google.co.jp/search?hl=ja&rlz=1C1GGLS_jaJP302JP303&q=MurMurHash+2.0&btnG また、高速な文字列登録(検索)を行う為の方法があれば教えて下さい。 よろしくお願いいたします。

  • 探索アルゴリズムの名称について

    以下の探索もしくは組み合わせのアルゴリズムに名称があるのかを教えていただければ幸いです. ある変数a1,a2,a3・・・,b1,b2,b3・・・があり(それぞれ小さい順にソートされている), このaとbにより影響する評価関数が最小となる最適な組を探索するアルゴリズムです. (1)まずa1・b1のペアを用いた時の値を算出する. (2)次にa2・b1のペアとa1・b2のペアでの値をそれぞれ算出し,小さい方を見つける. (今回はa1・b2のペアの方が小さかったとします.) (3)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し,小さい方を見つける. (2),(3)の様な処理を繰り返し行い,最小となるa・bの組を探索する. 以上の様なアルゴリズムなのですが,名称があるのかをお聞きしたいと思います. 言葉で書くとイメージしづらいですが,小学・中学ぐらいで勉強した最短経路問題のように 格子状の図を書くと分かりやすいと思います. 二方向のみをみて探索していきます. 個人的には,二分木探索に近いと思うのですがどうでしょうか? ただ,進み方によっては,同じ組み合わせを探索する事も出来るので, 完全な二分木探索ではないような気がします. 皆様のお力をお貸しいただければありがたいです. お願いいたします.

  • Excelで各行の最小値となる列の探索

    Excelで,各行ごとに,最小値を探索し,その最小値が どの列のデータかを計算したいのですが,どのようにすればよいのでしょうか? 例えば      山田  鈴木  田中 データ(1) 10.3  0.42  0.5 データ(2) 1    10.1   4 データ(3) 5    11.8   2 といった感じのデータに対して,      山田  鈴木  田中 データ(1) 10.3  0.42  0.5  鈴木 データ(2) 1    10.1   4   山田 データ(3) 5    11.8   2   田中    という感じで,各列の1行目の値が出力されるように したいのですが。 一応,LookUp関数,Match&Index関数を使ってみましたが,探索する文字列が小数のためか,探索できる行と N/Aになるものとが存在し,その差がなぜ生じるのかが わかりません。 上記関数にはこだわらないので,何か良い方法がありましたらご教授ください。

  • 探索プログラムの速さの計算方法を教えてください。

    以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。

  • ハッシュ化で元の文字列の方が長くても大丈夫ですか?

    例えば1000桁の文字列をphpのhash()でsha512を用いてハッシュ化した場合、重複の危険性は 無視出来る程度なのでしょうか。 ご存知のかた、お手数をおかけいたしますがご回答のほどよろしくお願い致します。

  • 最長の共通部分

    はじめて質問させていただきます。 二つのデータの最大長の共通部分を求めるための、 なるだけ高速なアルゴリズムを探しています。 たとえば、 データ1:『EFGABCDEFGABCDEFGHAABCDEFG』 データ2:『EFGHABCDEFGABCDEFGAABCDEFG』 ですと データ1の4バイト目のAから始まる14バイトと データ2の5バイト目のAから始まる14バイトが一致。 が求めたい答えです。 細かい条件をならべると、 1) 文字列ではなくバイナリデータである。 2) データサイズは、最大で数MB程度を想定。 3) 同じ並びの繰り返しなどを多く含んでいる可能性を否定できない。 4) 連続した1つのバイト列で最長なものが知りたい。 5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、 誤差はあってもよい。 6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。 といった感じなのですが。 ソートを使う、ハッシュを使う、飛び飛びに探索する等、 いろいろアルゴリズムを考えてみましたが、どれもパッとしません。 先ほどグーグルで検索していて、どうやらかなり難しいらしい ということに気づきました。 なにか、ご存知の方いらっしゃいましたら、 アドバイスをお願いいたします。

  • 数値・文字列を決まった範囲の数値に変換・割り当てる(ハッシュする?)方

    数値・文字列を決まった範囲の数値に変換・割り当てる(ハッシュする?)方法について ハッシュ関数を使えば、ある文字列・数値を何らかの法則で暗号のように変換できることは分かったのですが、その変換される結果の範囲を決まった数値として指定することは可能なのでしょうか。 例えば『文字列を「1~95」の数値のどれかに割り当てたい』という感じです。 ランダムでなく、何度やっても同じ結果にしたいのです。 また、範囲は例では「1~95」としていますが、「1~230」「1~500」など自由に変更したいと思っています。 ※以前質問した占いに関連するものでして、結果の数が定まっていないため、 結果の数に応じて、元となるデータから占い結果に割り当てるということをやりたいと思っています。 ご教示いただけますようお願いします。

    • ベストアンサー
    • PHP