初めての(まともな)ハッシュ関数
こんにちは。c#初心者です。
今回はハッシュ関数の質問なので、c, c++, c#, java(j#とかf#もあったっけ?)のどなたでも答えられるかと思います。
ハッシュ関数を調べてみたところ、いろいろな用途があるみたいですが、今回はハッシュテーブル用に使うので、
1:計算速度(←今回は多分O(1)になるはず&メソッドの呼び出しなし なので心配ないかと)
2:一様に分布すること
が、重要と思うのですが、上記の通り、2を優先したいと思います。
それで、今回のサンプルは
struct Sample
{
// アクセス修飾子、その他もろもろ省略
readonly int Value; // Javaだったら readonlyじゃなくてfinallyだったかな?
readonly int Index;
}
こんな感じの構造体(別にクラスでも良い)なのですが、ハッシュ関数を今までまともに作ったこと無くて、ノウハウがありません。
一応いくつか超簡単なものを考えてみました。
パターンA
return Value * Index
パターンB-1
return Value | Index
パターンB-2
return Value ^ Index
パターンC
return (Value ^ Index) + Index
・
・
・
などです。
それぞれの数値の関係は大雑把に、
・0 <= Value
・0 <= Index
・Value ≫ Index (非常に大きい)の確率が高
・Value < Index のこともある
です。
上記のもので、BやCあたり、特にCは比較的均等にばらつく気がするのですが、こんなのでいいのか、かなり不安です。
どなたか分かる人がいらっしゃいましたら教えていただけませんか?
お礼
返事遅くなってすみませんでした。回答ありがとうございました。 参考にさせていただきます。