2

これは宿題の質問ですが、何かが欠けていると思います。それは尋ねます：

線形プロービングで実装されたハッシュ テーブルを埋めるm 個のキーのシーケンスを提供し、それを埋める時間が最小になるようにします。

その後

mキーの別のシーケンスを提供しますが、それを埋める時間が最大になるようにします。ハッシュ テーブルが 2 次プロービングを実装している場合は、これら 2 つの質問を繰り返します。

ハッシュ テーブルのサイズがmであると仮定することしかできません。これは、指定された唯一の数値であり、負荷係数を説明する前にハッシュ テーブルのサイズを指定するためにその文字を使用してきたためです。しかし、シーケンスをテーブルにハッシュするハッシュ関数を知らずに、最初のシーケンスを実行することは考えられません。

たとえば、すべてのエントリを同じインデックスにハッシュするなど、不適切なハッシュ関数である場合、シーケンスがどのように見えるかに関係なく、それを埋めるための最小時間と最大時間の両方に O(n) 時間がかかります。そして、平均的なケースでは、ハッシュ関数は問題ないと仮定しますが、そのハッシュ関数がテーブルを埋めるのにかかる時間をどのように知ることができますか?

これらの質問は、ハッシュされたシーケンスよりもハッシュ関数にリンクされているのではないでしょうか?

2 番目の質問については、ハッシュ関数に関係なく、同じキーがm回繰り返されるサイズmのシーケンスが最大時間を提供すると仮定できます。これは、2 番目のエントリから線形プローブが発生するためです。O(n)時間かかると思います。あれは正しいですか？

4

2 に答える 2

1

この質問は、ハッシュ関数にそれほど関心があるようには聞こえませんが、あると便利です。しかし、あなたはほとんどそれを理解しているようです。質問は、「最悪の場合のキーのリストがどうなるか知っていますか?」ということにもっと関心があるように思えます。「悪いハッシュ関数を悪用する方法を知っていますか?」よりも

明らかに、すべてのエントリが異なる場所にハッシュされるシーケンスを思いついた場合、合計 O(m) 時間で O(1) の挿入があります。

すべてのキーを同じ場所にハッシュすることについてあなたが言っていることについては、それがあなたが提案している場合、各挿入は O(n) を取る必要があります。ただし、それはすべての要素を挿入するための合計時間ではありません。また、文字通り同じキーを何度も使用するのではなく、テーブル内で同じ位置を生成するキーを使用することを検討することもできます。慣例により、同じキーを挿入すると置換が発生するはずですが、100％確実ではありません。

情報が多すぎたり、不明な点があったりした場合は、事前に謝罪します。この質問は、ハッシュ関数を実際に知らないという部分を除いて、かなり切り詰められているように見えます。質問全体に答えずに多くを言うのはちょっと難しかったです。

于 2012-07-02T17:14:53.870 に答える
1

これらの質問の背後にある考え方は、プロービング スタイルの理解度をテストすることです。線形プロービングの場合、衝突が発生した場合は、次のセルをテストするだけです。そして、データを保存できるセルが見つかるまで、このように続けます。ハッシュ テーブルのサイズは m である必要はありませんが、at least size m.

最初の質問は、完全なハッシュ関数がある場合、テーブルへの入力の複雑さはどのくらいかということです。完全ハッシュ関数は、衝突することなく各要素をアドレス指定します。したがって、m の各要素には、O(1) 時間が必要です。全体の複雑さは O(m) です。

2 番目の質問は、hash(X)=cell(0) の場合で、すべての要素が最初の空のセル (現在入力されているテーブルのすぐ後ろ) まで検索します。

最初の要素については、1 回プローブします -> O(1)

2 番目の要素については、2 回プローブします -> O(2)

n 番目の要素については、n 回プローブします -> O(n)

全体的に m 個の要素があるので、->O(n*(n+1)/2)

二次プロービングの場合、同じ戦略があります。最小の場合は同じですが、最大の場合は O(nlogn) になります。（私はそれを解決しませんでした、それは私の経験に基づいた推測です。）

于 2012-07-02T17:50:15.507 に答える