連鎖ハッシュテーブルルックアップの最悪の場合の時間複雑度が予想されますか？

Question

良いハッシュ関数（任意の2つの要素の衝突確率が1/m、mはバケットの数）を使用してハッシュテーブルを実装する場合、見た目の平均ケース実行時間要素がΘ（1 + α）であり、αが負荷係数です。しかし、最悪の場合の実行時間はO（n）ですが、すべての要素が同じバケットに入れられるとします。

私は最近、いくつかは、ハッシュテーブルの上に読んでやっと（ログN/Nをログログ）α = 1場合は、期待最悪の場合の複雑さがΘであること（3ページ）主張するthis articleを発見しました。 「予想される最悪の場合の複雑さ」とは、要素が一様なハッシュ関数によって分散されている場合に必要な作業の最大量を意味します。ワーストケースの動作（同じバケット内のすべての要素）が実際に発生する可能性は非常に低いため、これは実際のワーストケースとは異なります。

私の質問は次のとおりです。αの値が異なると、予想される最悪の場合の検索の複雑さが変更される可能性があります。 αが予想される最悪の場合の実行時間をどのように変更するかを議論する数式、表、または記事を誰かが知っていますか？

Answer 1

で、シャープな推定値を得る、私は完全な分析を与えることthis research paperに出くわしました連鎖したハッシュテーブルを含むさまざまなタイプのハッシュテーブル全体の予想される最悪の場合の動作を示します。著者は、期待される長さが約Γ ^-1（m）（mはバケット数、ΓはGamma function）という答えを返します。 αが定数であると仮定すると、これは約ln m/ln ln mです。

希望すると便利です。

Answer 2

固定の場合、αの予想最悪時間は、常にΘ(log n/log log n)です。ただし、αの機能をnにすると、予想される最悪の時間が変わる可能性があります。たとえば、α = O(n)の場合、予想される最悪時間はO(n)です（これは、固定ハッシュバケット数です）。

一般に、バケットへのアイテムの分布はほぼポアソン分布であり、iアイテムを持つランダムバケットのオッズはαi e-α/i!です。最悪のケースは、独立観測に近いmのうち、最悪のものはmです。 （完全に独立しているわけではありませんが、それにかなり近いです。）mは、mの中で最も悪いです。起こる確率は約1/mです。 （より正確には分布がΒ分布によって与えられたが、私たちの分析のため1/mは十分に良いです。）

あなたはポアソン分布のテールに向かう通りi!用語の成長は他のすべて、その累積確率を支配iの上にあるすべてのもののうちのどれかが、iを選択する確率よりも小さくなります。両側のテイクログ

αi e-α/i! = 1/m = 1/(n/α) = α/n

と我々が得る：あなたは解くことによって期待値を把握することができます良い近似にそう

i log(α) - α - (i log(i) - i + O(log(i)) = log(α) - log(n) 
log(n) - α = i log(i) - i - i log(α) + O(log(i))

我々はαが一定に保持した場合、これは次のとおりです。

log(n) = i log(i) + O(i)

iの形式がk log(n)/log(log(n))の場合はk = Θ(1)となりますか？のは、それを試してみましょう：

log(n) = (k log(n)/log(log(n))) (log(k) + log(log(n)) - log(log(log(n)))) + O(log(log(n))) 
     = k (log(n) + o(log(n)) + o(log(n))

そして、我々は、任意の固定の平均負荷αのために、予想される最悪の時間は、いくつかの検索後(1 + o(1)) log(n)/log(log(n))