algorithm - ハッシュ テーブルの負荷係数 a および n スロット、衝突に対するオープン アドレス指定

Question

私は高頻度取引のインタビューで、データ構造の数学的な側面をすべて尋ねられました.1つの質問は次のとおりです。負荷係数a = 1-1 /（sqrt（n）logn）、失敗した検索の時間は? 「n」だけを使って答えを述べなさい

Answer 1

この項は、増加する1-1/(sqrt(n)*log(n))につれて 1.0 に近づきnます。の場合n==10、値は 0.9048 です。の場合n==1000000、値は 0.9999 です。(対数底 2 を使用しています。)

完全なハッシュ テーブル (負荷係数 1.0 が意味するもの) とオープン アドレスを使用すると、すべての項目を調べる必要があります。したがって、検索が失敗する時間は O(n) になります。