1

この問題を解決しようとしています (CLRS、第 3 版、演習 11.2-1):

ハッシュ関数 h を使用して、n 個の異なるキーを長さ m の配列にハッシュするとします。単純な一様ハッシュを仮定すると、予想される衝突の数は?

正解は n(n-1)/2m です。これは、CLRS のインストラクターのマニュアルから取得されます。

私の解決策は次のとおりです。

  • キー 1 の挿入の場合: 先行キーとの予想衝突数 = 0

  • キー 2 の挿入の場合: 先行キーとの予想衝突数 = 1/m

  • キー 3 の挿入の場合: 前任者との予想衝突数 = 1/m*(1/m) + (m-1)/m*(2/m) = (2m-1)/m^2

私の推論: 1 つのスロットでキー 1 と 2 が衝突する確率は 1/m です。つまり、キー 3 の衝突の確率は 1/m です。キー 1 とキー 2 が衝突しなかった可能性は (m-1)/m あります。つまり、それらは異なるスロットにあり、キー 3 の衝突の確率は 2/m です。

期待の線形性による 3 つのキーの衝突の期待数 = 0 + 1/m + (2m-1)/m^2 = (3m-1)/m^2

CLRS によると、3 つのキーの予想衝突数は 3/m である必要があります。

インディケータ RV を使用して正しい解を見つける方法を知っています。

私の質問は次のとおりです。ソリューションのどこで間違いを犯しましたか? なぜ違うのですか？

4

2 に答える 2

0

インストラクターマニュアルの解決策はオフのようです。簡単な例、12 個のキー [0..11] は、h(k) = k mod 3 によって 3 要素の配列にハッシュされます。

キー 0、3、6、9 を持つバケット 0 があります。バケット 1 にはキー 1、4、7、10 があります。バケット 2 にはキー 2、5、8、11 があります。バケット 0 の衝突は {(0,3), (0,6), (0, 9), (3,6), (3,9), (6,9)}、基数 = 6 です。バケット 1 と 2 もそれぞれ 6 回の衝突に寄与します。

したがって、この例の衝突の総数は 18 です。予測される衝突の数が n(n-1)/2m 式で与えられる場合、12*11/6 = 22 になります。

違う。

このように推論することによって、私は別の公式にたどり着きました：

  1. 均一なハッシュを仮定すると、各バケット内のキーの数は他のバケットと同じ、つまり n/m であると予想されます。したがって、衝突の合計数は m*Collisions(1 つのバケット) になります。

  2. では、各バケットの衝突数を取得するにはどうすればよいでしょうか? その中にある各キーは他のすべてのキーと衝突し、衝突のセットは一度にそれらのペアを取ることによって定義されます。したがって、一度に 2 つ取られる (n/m) 要素の数の組み合わせを見ています。

C(n/m, 2) = (n/m)!/[2!(n/m -2)!] = [(n/m)(n/m -1)(n/m -2)! ]/[2*(n/m -2)!]。

(n/m - 2)! 分子/分母の項は互いに打ち消し合い、

C(n/m, 2) = [(n/m)(n/m - 1]/2 = n(nm)/2m^2

したがって、衝突の総数は m*C(n/m, 2) = n(nm)/2m です。

これを私たちの例に当てはめてみましょう。

12(12-3)/2*3 = 12*9/6 = 18

これはまさに、この例の一連の衝突のカーディナリティです。

于 2018-07-12T21:48:02.790 に答える
-1

キー 1 と 2 が 1 つのスロットで衝突する確率は 1/m です。つまり、キー 3 が衝突する確率は 1/m です。

衝突の処理方法によって異なります。クローズド ハッシュの実装では、キー 2 に対して代替バケットが選択されるため、キー 3 を挿入するときに最初にハッシュされたバケットで衝突が発生する可能性は依然として 2/m です (その後、2 番目の選択でさらに可能性がある可能性があります)。バケット、第 3 選択のバケットなど - 以下を参照してください)。オープン ハッシュの場合、衝突する要素は同じバケットから連鎖されるため、キー 1 と 2 が衝突すると、キー 3 が最初に同じバケットにハッシュされる可能性が 1/m 減少します (さらに、第二選択バケットなど）。

したがって、大きな問題は、異なる衝突処理アプローチを想定していることです:クローズドハッシュとオープンハッシュです。

とはいえ、あなたが提示した質問はあいまいです-衝突後に値がどのように追加されるかが、さらなる衝突の可能性に影響を与える可能性があります。たとえば、単純な均一ハッシュも実現する代替ハッシュ アルゴリズムを使用した再ハッシュは、衝突後の再挿入試行ごとに別の #inserted/#buckets 衝突確率を意味するため、一連の処理は次のようになります。

  • キー 1: 予想される衝突数 = 0

  • キー 2: 予想される衝突数 = 1/m + 1/m*1/m + 1/m*1/m*1/m + ...

  • キー 3: 予想される衝突数 = 2/m + 2/m*2/m + 2/m*2/m*2/m + ...

たとえば、線形プロービング、二次プロービングなどでは異なります。

于 2016-04-12T06:26:41.207 に答える