なぜハッシュ関数はモジュロを使うのはふつう？

質問

ハッシュ関数の定義はWikipedidaによると「データが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと」となっていますが、
色んな記事見ているとキー値(x)をデータの個数(n)で割った時の余り、
つまりx mod nみたいな計算が一般的みたいな書かれ方しているような気がします。

ハッシュ関数と言ったら上記のようなx mod nという理解でいいのでしょうか？
また、なぜ冒頭で定義されたはずの関数が簡単なモジュロ計算で表されるようになってしまったのでしょうか？

回答No.2

Gotthold · ベストアンサー

> ハッシュ関数と言ったら上記のようなx mod nという理解でいいのでしょうか？
Wikipedia見てたならそういう理解にはならないはずです。
もう一度読んでください。
「3 ハッシュ関数のアルゴリズム」に具体例がいくつもあって、そこを見るだけでもmodだけではないことは分かる。

ハッシュ関数 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0

> また、なぜ冒頭で定義されたはずの関数が簡単なモジュロ計算で表されるようになってしまったのでしょうか？
簡単で分かりやすいから例として挙げられただけだと思いますが。
ハッシュ関数の定義を満たす関数なんていくらでもあるわけで、モジュロ計算はその内の1つ。

お礼

>ハッシュ関数の定義を満たす関数なんていくらでもあるわけで、>モジュロ計算はその内の1つ。

なるほど、あくまでも定義を満たしてる関数の一つだったということで腑に落ちました。

回答No.1

ok-kaneto

>ハッシュ関数と言ったら上記のようなx mod nという理解でいいのでしょうか？
厳密には違いますね。あくまでも一方向関数というだけで剰余計算だけがそうとも限りません。

>関数が簡単なモジュロ計算で表されるようになってしまった
便利だからだと思います。余りは一様に分布するので衝突する確率も低いですし。

お礼

modがよくつかわれる理由がわかりました。ありがとうございます。