これは宿題に関する質問であり、正しいアプローチについて私はひどく混乱しています。実行時分析の確率は？
mスロットのハッシュテーブルが存在します。 シンプルユニフォームハッシング仮説（SUHA）とする。
n個の挿入操作を実行しますが、n個の要素すべてがスロット0にマップされます（これは可能ではありませんが、可能です）。
ここで、疑問は、テーブルにハッシュが存在していてもいなくてもよいランダムなキー 'x'を検索するよう求められます。 検索の実行時の上限はどのくらいですか？
これは私のアプローチである：
我々はスハを想定しているので、スロットにハッシュキーの確率は1/mです。実際にキーがスロット0にハッシュした場合、探索はO（n）時間かかり、そうでなければO（m-1）時間かかる。この論理によって、解はO（n/m + [（m-1））に単純化する[1/m] * O（n）+ [（m-1）/ m]^2]/m）。
1.この方法で確率を漸近ランタイムに乗算できますか？
2.おそらくランタイムを決定する役割を果たしますか？
あなたはこの間違いを考えていると思います。確率を考慮する必要はありません。問題は上限を求めているので、その質問をに翻訳してください。最悪のシナリオは何ですか？
最悪の場合は、前のすべてのハッシュのようにxハッシュが0になる場合です。 xが最後にハッシュされた要素であるとしましょう。衝突の解決に応じて、探している要素が見つかるまで、可能な場所をたどる必要があります。これは問題に示されているように前回のハッシュ数に依存しているため、O（n）になります。
xが0にハッシュしなかった場合のシナリオは、O（1）であるため、キーにハッシュすると、そこにあるかどうか、別のO（1）操作全体的に、O（1）操作にします。
上限は最悪の場合を意味します。
確率を「1/m」とすると、平均の場合が計算されます。
あなたは今、私は解決策を書くつもりだとして、下記を見ずに質問をしてみてください可能性があります
とき、最悪の場合は次のようになります。
この場合、そのスロットのすべての要素を調べて、実行時間がO（n）になる必要があります。
鍵がハッシュされているときに確率が出るようにそうではありませんか？最悪の場合の分析は、すでにハッシュされた値が検索される（どこにあってもよい）場合に有効になります。つまり、ハッシュ処理が完了した後で最悪の場合の分析が実行されますか？ – Janmajay
キーをハッシュする確率は無関係です。 mスロットのマップでは、キーは常に同じ値にハッシュされます。ハッシュは単なる定数操作です。したがって、探しているキー、キーがハッシュするスロット、または最悪の場合の検索O（n）を行う衝突が発生した場合の可能性のある場所をすべて検索する必要はありません。 –
@Janmajay：はい、ハッシュの確率は「1/m」です。ワーストケース分析は、最悪の事態が起こったと仮定していることを意味します。最悪の場合、ハッシュされたインデックス値が、挿入されたすべての値が存在するインデックス値であることが分かります。 – displayName
確かに、確率が要因として作用するかどうかはわかりません。その場合、ランタイムは単にn +（m-1）ではありませんか？ （チェーンを見渡し、残りのスロットを見る時間） – Janmajay
いいえ、残りのすべてのスロットを調べる必要があるのはなぜですか？マップには、以前の値が存在する場所にハッシュした場合に値を格納する方法を定義する衝突解決があります。たとえば、リンクされたリストが各スロットに格納され、コリジョンの値がリストの末尾に追加されるというような、単一のリンクされたリストを使用した場合を考えてみましょう。あなたの検索で最悪の場合、長さnのリンクされたリストですので、n個のアイテムを検索するだけです –
ええ、それは意味があります。私の質問を修正し、n/2要素がスロット0にマップし、n/2要素がスロット1にマップすると、答えは変わらないでしょうか？私は本当に確率が役割を果たす状況を考えようとしています！ – Janmajay