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

例えば1000桁の文字列をphpのhash()でsha512を用いてハッシュ化した場合、重複の危険性は
無視出来る程度なのでしょうか。

ご存知のかた、お手数をおかけいたしますがご回答のほどよろしくお願い致します。

No.3 ベストアンサー 回答者： chie65535 回答日時： 2013/03/22 10:56

「ハッシュ関数の特性」により、文字列が何文字だろうが、ハッシュ値が何ビットだろうが「重複の可能性は０じゃない」です。

「無視できる程度」と判断して無視した場合でも「重複が起きる時は一発で起きる」と言う事を判った上で判断して下さい。

上記を踏まえた上で。

sha512のハッシュ値は512ビットです。

1000桁の半角文字列が取り得る組み合わせ数は、可読文字96文字のみに限定すると、96の1000乗、1.86e+1982個です。

1.86e+1982個の文字列を、1.34e+154個のキーで表す事になります。

つまり、キー１つに付き、1.39e+1828個の文字列が重複します。

キーの個数と、文字列が取り得る組み合わせ数から言えば「ほぼ常に重複が起きる」と言えます。

ハッシュってのは「元の文字列が長ければ長いほど、ハッシュ値のビット数が小さければ小さいほど、重複が増える」ので、元の文字列が1000文字もあったら「常に重複する」と考えましょう。

因みに、半角77文字以内なら、文字列の個数よりキーの個数の方が多いので「重複を無視しても良い」と思います。

言い換えれば「重複が無視出来るのは、元の文字列が半角で77文字以内」と言えます。

この回答へのお礼

詳細な解説ありがとうございます。
ハッシュ化で文字数を減らしたかったのですが難しいことが分かりました。

みなさんご回答頂きましてどうもありがとうございました。

お礼日時：2013/03/23 10:35

No.2 回答者： kngj1740 回答日時： 2013/03/22 09:14

扱うデータが全くランダムという事はまれで、どうしてもあるタイプのデータばかりというケースは珍しくありません。

実際に実験してみないとなんとも言えません。たとえば人名なら全ての漢字がランダムに使われる訳ではありません。

No.1 回答者： wormhole 回答日時： 2013/03/22 02:55

sha512だと、ハッシュ値は2の512乗通りあるわけですが、それがわかれば重複する確率は計算できますよね。

それを無視できるとするかどうかはご自分でご判断ください。