3

優れたハッシュ関数（任意の2つの要素が衝突する確率が1 / m、mはバケットの数）を使用してハッシュテーブルを実装する場合、検索の平均的な実行時間はよく知られています。要素はΘ（1 +α）です。ここで、αは負荷率です。ただし、すべての要素が同じバケットに入れられる場合、最悪の場合の実行時間はO（n）です。

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

私の質問は次のとおりです。著者は、αの値を変えると、ルックアップの予想される最悪の場合の複雑さが変わる可能性があることを示唆しているようです。αを変更すると予想される最悪の場合の実行時間がどのように変化するかを説明する式、表、または記事をどこかで知っている人はいますか？

4

2 に答える 2

3

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

i一般に、バケットへのアイテムの分布はほぼポアソン分布であり、ランダムなバケットにアイテムが含まれる確率はです。最悪のケースは、独立した観察に近いもののうち、最悪のケースです。(完全に独立しているわけではありませんが、それにかなり近いです。)観察結果から 1 番目に悪いものは、発生確率が約 1倍になる傾向があります。(より正確には、分布は Β 分布によって与えられますが、私たちの分析では十分です。)αi e-α / i!mmmm1/m1/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(ログ (n)))
       = k (log(n) + o(log(n)) + o(log(n))

そして、一定の負荷平均αに対して、予想される最悪の時間は(1 + o(1)) log(n) / log(log(n))

于 2012-05-14T14:45:54.427 に答える
1

いくつかの検索の後、この研究論文に出くわしました。これは、連鎖ハッシュ テーブルを含む、さまざまな種類のハッシュ テーブル全体で予想される最悪の場合の動作を完全に分析したものです。著者は、期待される長さはおよそ Γ -1 (m) であると答えています。ここで、m はバケットの数であり、Γ はガンマ関数です。α を定数とすると、これはおよそ ln m / ln ln m となります。

お役に立てれば！

于 2012-06-19T20:25:36.140 に答える