ガウス分布+ハッシュテーブル

Question

私はハッシュ関数について奇妙な考えがありました。問題文はあなたがコースに300のうちn個のマークを 取得クラスで162人の 学生のID-番号を格納している

である（各n = 0のため、 1、2、... 300）ハッシュテーブルに格納します。このために、 の無駄なメモリセルもまた最小であるように、 が最も簡単で最も衝突が起こりにくいハッシュ関数である。二人の学生 スコアnはとn は、ハッシュテーブル内の同じスロットを得るとき ここで、衝突があります。

1つの解決策は、連鎖と共にh（n）=（n * 5 + 7）％163を使用することができます。最大162個の異なるマークが存在します。

EDITこれを行うにはいくつかの標準的な方法があります。しかし私は自分のアイデアを試してみたいと思っています（おそらく数学的に）。それはちょうどより少ないメモリとのより少ない衝突を有するかもしれない。

---

ここに私が持っていたアイデアがあります。私はgaussianとなるようにマークの分布を仮定することができます。だから、平均スコアの近くにいる人が多く、極端な人は少なくなっています。

だから、私は、ハッシュ関数のようなもの持つことができる：

H（N）= 0を（もしN < 100 || N> 200）
H（N）= 1（100の場合< = N < 125 || 175 < = N < 200）
H（n）は2（IF 125 < = N < 140 || 160 < = N < 175）
H（N）= 3（140場合を= < = n < 160）

一部のこのような条件（たとえばk）では、ハッシュテーブルの衝突数は最小で、占有されるスペースは最小です。

これは単なる推測です。このようなことが意味をなさないでしょうか？これを証明する方法はありますか？または私はどこか間違っていますか？

Answer 1

ここで手動で行っていることは、画像処理histogram equalizationで呼び出されます。統計的にすべてのスロットが同じ確率で使用されていることを確認し、衝突を最小限に抑えるので、それは絶対に意味をなさないと思います。

Answer 2

編集：質問を読んで、「削除」を投票しても何もしないようです。

Answer 3

変数が正規分布の場合、通常のCDFを使用して変換してください。結果は0と1の間に均等に分散され、自然にハッシュテーブルのキーになります。

Answer 4

histogram_equalizationなどを行うのはかなり高価になる可能性があります。 cuckoo hashingまたはhopscotch hashingのように、hash collisionsまたはその効果を減らすための標準的な方法を検討することもできます。