私の 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 の数値のペアがあるかどうかを確認しようとしていることがわかりました。
x^2 == 4*n+2
つまり、任意の整数の 4 倍より 2 多い数は平方数です。
すべての整数 x と n について、それが真になるペアが存在しないことが証明できる場合、それは、長さ 4 の配列のインデックス 2 に 2 次プロービングが決して到達しないことを意味します。
これは、放物線について次のように言っているのと同じだと思います。
y=(x^2-2)/4
x と y の両方が整数である (x, y) ペアは含まれていませんが、完全にはわかりません。
私はこれに取り組んで過去2時間を費やしましたが、これが私が把握できたすべてです。
二次プロービングがスポットを見つけられない場合があることを私は知っています。それは私が興味を持っていることではありません。これが決して機能しないこと、または十分に大きな数を使用すると、これが最終的に終了することを証明するにはどうすればよいですか。また、数学を BC 微積分で学習した内容の下に置いておくことができれば、それは素晴らしいことです。
どうもありがとう！