初めての（まともな）ハッシュ関数

質問

こんにちは。c#初心者です。

　今回はハッシュ関数の質問なので、c, c++, c#, java(j#とかf#もあったっけ？)のどなたでも答えられるかと思います。

　ハッシュ関数を調べてみたところ、いろいろな用途があるみたいですが、今回はハッシュテーブル用に使うので、

１：計算速度（←今回は多分O(1)になるはず＆メソッドの呼び出しなし なので心配ないかと）
２：一様に分布すること

　が、重要と思うのですが、上記の通り、２を優先したいと思います。

　それで、今回のサンプルは
struct Sample
{
// アクセス修飾子、その他もろもろ省略
readonly int Value; // Javaだったら readonlyじゃなくてfinallyだったかな？
readonly int Index;
}

　こんな感じの構造体（別にクラスでも良い）なのですが、ハッシュ関数を今までまともに作ったこと無くて、ノウハウがありません。

　一応いくつか超簡単なものを考えてみました。

パターンA
return Value * Index
パターンＢ－１
return Value | Index
パターンＢ－２
return Value ^ Index
パターンＣ
return (Value ^ Index) + Index
　・
　・
　・
などです。

　それぞれの数値の関係は大雑把に、
・0 <= Value
・0 <= Index
・Value ≫ Index (非常に大きい)の確率が高
・Value < Index　のこともある
です。

　上記のもので、ＢやＣあたり、特にＣは比較的均等にばらつく気がするのですが、こんなのでいいのか、かなり不安です。

　どなたか分かる人がいらっしゃいましたら教えていただけませんか？

回答No.3

wormhole · ベストアンサー

IndexとValueの分布が多そうな部分同士は被らなさそうなので単純にIndex+Valueでもいいかも。

お礼

あれっ！？　そんな簡単なものでもいいのですか？　状況によってぜんぜんちがうものなんですね。

　僕が一回見せてもらったハッシュ関数は何だか４～６行ぐらいあったので、ハッシュ関数って、もっと複雑なものかと……。
　とりあえず、他にも色々な記事を読んで理解は深まりました。ありがとうございました。

回答No.2

wormhole

Valueが一様に分布するならValueをそのまま使ってもよさそうな気もしますが、考えられるIndexとValueで得られるハッシュ値の検証プログラムを組んで確かめた方がよいとは思います。

ところでハッシュ値が重複した場合はどうするかは考えてありますか？

お礼

回答ありがとうございます。少しだけ抜けていました。

　Valueはほとんど一様に分布するのですが、良く考えていなかったのですが、１００～４、５０００位の間で一様に分布するの間違いでした。あまり大きな値はめったに使わないので思い込んでいました。

----------------------------------
　　　／￣￣￣￣＼
＿／　　　　　　　　　＼＿＿＿＿＿＿＿
　100　　　　　　　　　5000
----------------------------------
↑Valueはこんな感じで分布するはず

　重複の問題は既存のハッシュテーブルに任せるので問題ないです（重複分だけループ＆チェックされるはず）。

回答No.1

wormhole

ハッシュテーブルを使って何をしたいのでしょうか？
IndexをキーとしてValueを求めるためのハッシュテーブルということであればハッシュ値にValueを含めるとダメです(Valueを求めるためにValueもわかってないといけなくなる)。
またパターンA～CにしてもIndexとValueの範囲がわかっても分布がわからないので何ともいえません。
極端な例ですが、Indexが重複することがないのならIndexの値そのものをハッシュ値としても問題ありません。

お礼

回答ありがとうございます。

> IndexをキーとしてValueを求めるためのハッシュテーブルということであれば
> ハッシュ値にValueを含めるとダメです
> (Valueを求めるためにValueもわかってないといけなくなる)。

　いえいえ、そうではなくて、別の配列などに対するインデックスと、操作に用いるための値を格納した構造体ですので、イメージとしてはUndo, Redo用の操作の記録とあまり変わらないと思います（「Index=4をValue=12に変える」のような感じ。ほんとはもうちょっと複雑ですが）。

> またパターンA～CにしてもIndexとValueの範囲がわかっても
> 分布がわからないので何ともいえません。

　失礼しました。
・Valueは一様に分布
・Indexは１０～３０くらいを中心にガウス分布っぽい形
（かなり低い方ににピークが寄っています）
　のはずです。