5

私は、ハッシュテーブルでの線形プロービング、2次プロービング、および個別のチェーンに必要な平均アクセスと最大アクセスを比較するプログラムを実行していました。

エレメント挿入部分は3ケース行っております。ハッシュテーブルから要素を検索している間、検索を終了するための制限が必要です。個別のチェーンの場合、次のポインターがnullになったときに停止できます。線形プロービングの場合、テーブル全体（つまりテーブルのサイズ）をプロービングしたときに停止できます。二次プロービングの制限として何を使用する必要がありますか？テーブルサイズはありますか？

私の二次プロービング機能はこんな感じです

newKey = (key + i*i) % size;

ここで、iは0から無限大まで変化します。私を助けてください..

4

3 に答える 3

8

iこのような問題については、2つの部分での成長を分析します。

最初の間隔：iから0size-1

この場合、私は今のところ解決策を持っていません。うまくいけば、更新されます。

2番目の間隔：iからsizeinfinity

この場合、次のiように表すことができます。i = size + k

newKey = (key + i*i) % size 
       = (key + (size+k)*(size+k)) % size
       = (key + size*size + 2*k*size + k*k) % size
       = (key + k*k) % size

iしたがって、に到達した後、以前にプローブされたセルのプローブを開始することは確実ですsize。iしたがって、0から。になる状況のみを考慮する必要がありますsize-1。残りは何度も何度も同じ話にすぎないからです。

What the story tells up to now:簡単な分析では、同じセルをプローブし始めsizeたので、ほとんどの場合プローブする必要があることがわかりました。size

于 2012-08-25T10:54:47.737 に答える
0

このリンクを参照してください。テーブルサイズが2の累乗であり、再プローブ関数f（i）= i *（i + 1）/ 2を使用している場合、テーブル全体をトラバースすることが保証されます。テーブルサイズが素数の場合、テーブルの少なくとも半分をトラバースすることが保証されています。一般に、ある時点で元のポイントに戻っているかどうかを確認できます。その場合は、再ハッシュする必要があります。

于 2013-04-02T17:30:12.253 に答える
0

Excelでいくつかのシミュレーションを実行した後、テストする必要があるのはi = size/2までの反復だけであるように見えます。これは、単一のハッシュ位置に連続する完全な正方形を追加する標準的な方法を使用する場合です。

位置が再検討された場合に終了できるという答えでは、少なくともすべての配列サイズについて、2次プローブ法で到達できる可能性のあるすべての位置をテストすることはできません。（配列サイズ21をテストしたところ、i=5はi=2と同じ位置に戻ることがわかりましたが、i = 6では以前は計算されていなかった位置が生成されます。）

于 2020-07-11T03:49:15.797 に答える