問題タブ [quadratic-probing]

イテレータの使用を除いて stl マップを模倣するハッシュ マップ クラスを作成しました。だから、私の問題は、イテレータを使用せずにハッシュマップをループし、特定のキーに関連付けられている値を出力することです。クラス自体はテンプレート化されていますが、main.cpp で使用される値は文字列のベクトルです。キーに関連付けられた項目 (値) を出力する出力関数を作成するにはどうすればよいですか? printElements() 関数を書いてみましたが、キーしか出力しません。前もって感謝します。

これが私のハッシュマップクラスです:

};

これは、メインで使用されるコードです。

}

特にハッシュテーブルと二次プロービングについて学んでいます。負荷係数が <= 0.5 で、テーブルのサイズが素数の場合、2 次プロービングは常に空のスロットを検出し、複数回アクセスされるキーはないことを読みました。さらに、効率的な挿入を確実にするために、負荷率を常に <= 0.5 に維持する必要があると述べています。これは何を意味するのでしょうか？確かに、アイテムを追加し続けると、必要かどうかに関係なく、負荷率が 1 になるまで増加します。では、私の教科書が小さな負荷率を維持する必要があると言っている場合、それは何を暗示しているのでしょうか?

私の AP コンピューター サイエンスのクラスは最近、ハッシュ テーブルと、線形プローブがどのようにクラスタリングの問題を引き起こし、実際には一定時間の挿入/検索ではないことが判明したかについて学びました。私たちのインストラクターは、明らかな理由から、クラスタリングを減らすには二次プロービングが良い方法であると教えてくれました。要素が1つ残っていると、2次プロービングでそれを見つけるのに時間がかかる可能性があるかどうか疑問に思いました。私は簡単なプログラムを書きました (必要に応じてソースを挿入できますが、とにかく誰もそれを読まないと思います)、これが起こるかどうかをテストしました。

最初に、決して着陸しない配列インデックスが存在しない場合、常にいずれかのインデックスに追加しようとすると、それが見つかることを証明しました。これは、これを行うことにより、最終的に配列内のすべてのインデックスにヒットするか、ヒットしないためです。二次プロービングがすべてのインデックスにヒットする場合、任意の時点で任意のインデックスを選択でき、常に終了するため、長さ配列は常に機能します。すべてのインスタンスにヒットできない場合は、これを行うとできないことがわかります。

次に、興味のある長さのブール値の配列を作成し、インデックス 0 が true でない場合は true に設定し、それ以外の場合はインデックス 1%length を true に設定し、そうでなければインデックス 4%length を設定しますそうでない場合は true ...そうでない場合は、インデックス n%length を true に設定します...

私は 1 フォワードと 1 バックをチェックしませんでしたが、ご覧のとおり、これはそもそも問題ではありませんでした。

したがって、4 つの要素の配列では、二次プローブはインデックス 0 と 1 を見つけますが、(約 46000^2 % の長さの範囲内で) インデックス 2 または 3 に到達することはありません。 (((0-1)%4+4)%4==3) ですが、まだインデックス 2 ではありません。

少し考えた後、次の式が真と評価される場合、x と n の両方が整数である x と n の数値のペアがあるかどうかを確認しようとしていることがわかりました。

つまり、任意の整数の 4 倍より 2 多い数は平方数です。

すべての整数 x と n について、それが真になるペアが存在しないことが証明できる場合、それは、長さ 4 の配列のインデックス 2 に 2 次プロービングが決して到達しないことを意味します。

これは、放物線について次のように言っているのと同じだと思います。

x と y の両方が整数である (x, y) ペアは含まれていませんが、完全にはわかりません。

私はこれに取り組んで過去2時間を費やしましたが、これが私が把握できたすべてです。

二次プロービングがスポットを見つけられない場合があることを私は知っています。それは私が興味を持っていることではありません。これが決して機能しないこと、または十分に大きな数を使用すると、これが最終的に終了することを証明するにはどうすればよいですか。また、数学を BC 微積分で学習した内容の下に置いておくことができれば、それは素晴らしいことです。

どうもありがとう！

こんにちは、何らかの理由で、挿入時にハッシュテーブルにアイテムとキーを入力できません。ドライバーを実行すると追加されているように見えますが、何も保存されておらず、エラーメッセージもまったくありません。二次プロービングを利用するハッシュ テーブルを作成するとします。20 を超えることができない横断の数を数えることを想定しています。

コードは次のとおりです。

}

ドライバーは次のとおりです。

}

二次プローブを使用してリストにキーを挿入するときに、プローブの数 (または渡す必要があるインデックスの数) を数えようとしています

私は持っている

これは、インデックスが変更されるたびにカウントされるだけで、交差するインデックスの数はカウントされないと思います。キーが渡すすべてのインデックスをカウントするにはどうすればよいですか?