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

質問

ハッシュ探索というのは「対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式」ということですが、どういうものなのかイメージが思いつきません。

これはつまり、データ本体を「ハッシュ」という文字列に変換して、ハッシュ値として出力したものを、比較する（全ての文字列において比較する）というイメージでよいのでしょうか？

もしそうだとしたら、ハッシュ値の長さ（文字列の長さ）に応じて（比較）処理時間が変わってくるのでしょうか？

例えば、（あくまで例です。）

6文字程度のハッシュ値→0.2秒で（比較処理時間が）終わる

3万文字程度のハッシュ値→3秒ぐらい（比較処理時間が）かかる

↑こういう風にハッシュ探索は文字列の長さに応じて処理時間が変化するのでしょうか？

回答のほうお願いします。

回答No.1

notnot · ベストアンサー

ハッシュ化と言うのは、いろいろな文字列やバイト列を、固定長のできるだけ重複しない（他と同じにならない）データに変換することです。

元のデータの長さによってハッシュ化の時間が変わるかというと、それは全く同じというわけには行きません。長さに比例して10ナノ秒だったり1ミリ秒だったりするかと思います。

ハッシュ探索はハッシュ値を使った探索（配列から目的のデータを探す）なので、すでにハッシュ化されたデータを使いますから、もとのデータの長さとは関係ありません。

回答No.2

asciiz

まず、ハッシュ化・ハッシュ関数の話から。

ハッシュ化とは、変換前の任意長のデータを、短い別データに変換することを指します。
例えば、元が100文字であっても、3万文字であっても、ハッシュ関数を通すと、16バイトのハッシュ値が計算される、と言った風にです。

大きいデータに演算を施して、小さなデータにしてしまいますから、中には、「元が違う文字列なのにハッシュ値が同じ」というパターンも存在し得ます。
しかしそこは計算方法の工夫により、そのようなことが起こる確率は非常に低くなっており、大概の場合には「ハッシュ値が一致したならば、元の文字列同士も一致している」と言えるんです。

ではここで例えば、100KBのデータをダウンロードしたとしましょう。
ダウンロードしたデータが正しいことをどうやって確認したら良いでしょうか?

もう一度ダウンロードして、ファイル比較するという手段があります。
でもダウンロード元に、「MD5: 112233445566778899aabbccddeeff00」みたいなハッシュ値が書いてあれば、ダウンロードしたファイルをMD5方式でハッシュ値に変換し、同じ値に変換されれば、「正しくダウンロードできた」と信用できます。

なお、ハッシュ値による比較では、「一致しているかどうか」しか調べられません。
元の文字列が1文字違う、あるいは元の文字列が1文字長い、と言ったパターンから、かなり違うハッシュ値が算出されます。
ハッシュ値からは元の文字列を類推できないので、どちらが長かったか、すら分からないんです。

----

「ハッシュ探索」という言葉はどういう文脈で出てきたんでしょうね?
例えばウイルス対策ソフトとかでしょうか。
この場合、「既知のウイルスファイルであるか」を調べるのに、このハッシュ値を使います。
もし、ウイルスプログラムそのもののデータを持っていたら、チェック用データはどんどん大きくなりますし、そのデータからうまく切り出したらウイルスファイルを復元できることになってしまって危険極まりありません。
そこで、たくさんあるウイルスプログラムのハッシュ値を計算し、そのハッシュ値のみをデータベース化しておきます。

そして新しいプログラムがインストールされたとき、各ファイルのハッシュ値を計算してみます。
もし、その中に既存のハッシュ値と一致するものがあれば、「このプログラムはウイルスファイルを含んでいる!」と検出できたりするわけです。