均一ハッシュ法と線形走査法

均一ハッシュ法と線形走査法それぞれについて
探索成功の場合、表を調べる回数を平均3回未満に
おさえるためにはそれぞれの方法の場合、
データ数nに対して表の大きさをどれくらいにとる
必要があるのでしょうか？

よくわかりません。どうやって計算したら良いでしょうか？

No.2 回答者： rinkun 回答日時： 2009/10/07 15:14

均一ハッシュ法も線形走査法もオープンアドレス法における再ハッシュ方法ですよね。

まず表の大きさMでデータ数nとして、それぞれの方法について探索成功時に表を調べる平均回数をM,nの式f(M,n)で表してください。ハッシュ計算・再ハッシュ計算で衝突する確率から積算すれば書けるでしょう。
あとは
f(M,n)<3
という不等式をNについて解けば解が出ます。
解くのが難しいようならグラフを書くなどして評価してみてください。

Googleにあたったところ『Cで学ぶデータ構造とアルゴリズム』に結果が載っているようです。この本では探索回数の期待値を占有率α=n/(M+1)の関数として記述しています。

No.1 回答者： Tacosan 回答日時： 2009/10/07 11:49

「表を調べる回数」が何を意味するのかが分かりません. 例えば n個の要素からなる表から線形走査で探すときの「表を調べる回数」は「1回」とされても文句は言えないんだけど (そう解釈できる), それでいい?

まあ, そもそも「表ってなんだ」ってのもありますけどね.