チェーンされたハッシュテーブルからランダムな要素を効率的に選んでいますか？ただ、練習（とない宿題など）のための

Question

私はこの問題を解決するために（CLRS、第3版、運動11.2から6）をしようとしている：

我々はのハッシュテーブルにn個のキーを格納していると仮定サイズm、 の連鎖は連鎖によって解決され、最長連鎖の長さLを含む各 連鎖の長さを知ることができる。ハッシュテーブル内の キーの中からランダムに一様にキーを選択し、期待時間O（L *（1 + m/n））に戻す手順を説明する を記述します。

私がこれまで考えていたことは、各キーが返される確率が1/nだということでした。私たちが1からnまでのランダムな値xを得ようとすると、バケツでソートされた順番にx番目のキーを見つけようとすると、バケツのチェーンに沿ってソートされ、次にO（m） 1つずつバケツを通し、O（L）時間をかけてチェーン内の正しいキーを取得します。要素が返されるまで

Answer 1

は、次の手順を繰り返します。

• をランダムにバケットを選択します。バケット内の要素の数をkとします。
• pをランダムに一様に選択します。1 ... Lです。 p <= kの場合は、p番目の要素をバケットに返します。

このプロシージャは、要素をランダムに一様に戻します。我々は、2D配列に配置された要素に拒否サンプリングを適用するようなものです。

バケットあたりの予想される要素数はn/mです。サンプリングが成功する確率は(n/m)/Lです。したがって、バケットを見つけるのに必要な試行回数はL * m/nです。バケットから要素を取得するためのO(L)コストとともに、期待される実行時間はO(L * (1 + m/n))です。