こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

-広告-

解決済みの質問

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

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

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

投稿日時 - 2014-09-08 22:51:20

QNo.8747526

困ってます

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

> ハッシュ関数と言ったら上記のような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つ。

投稿日時 - 2014-09-09 01:17:54

お礼

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

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

投稿日時 - 2014-09-10 21:12:01

このQ&Aは役に立ちましたか?

5人が「このQ&Aが役に立った」と投票しています

-広告-
-広告-

回答(2)

ANo.1

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

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

投稿日時 - 2014-09-08 23:05:06

お礼

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

投稿日時 - 2014-09-10 21:10:31

-広告-
-広告-

あなたにオススメの質問

-広告-
-広告-