1

10 個のバケットを持つハッシュ テーブルがあり、最初にシンボル S1 から S7 が、線形プローブを使用したハッシュ関数を使用して入力されたとします。存在しない項目を検索するのに必要な比較の最大回数は? ハッシュ ダイアグラムは次のように説明できます。

Index KEY

  • 0 - - S7

  • 1 - - S1

  • 2 - - 空

  • 3 - - S4

  • 4 - - S2

  • 5 - - 空

  • 6 - - S5

  • 7 - - 空

  • 8 - - S6

  • 9 - - S3

要素 S8 (明らかに存在しない) を見つけたいとします..S8 のハッシュ関数を計算すると、インデックス 8 にジャンプするとします。インデックス 8 で要素が見つからない場合、線形プローブによって次のインデックスがチェックされます。 .. Now, the number of comparisons should come out to be total length of the array because by linear probing it should try to look in every index...しかし、実際の答えは 5 です! :| 誰か説明してください!!

4

1 に答える 1

4

線形プローブは、空のハッシュ バケットに到達するまで要素を探します。この場合、8、9、0、1、および 2 を調べます。2 の場合、バケットが空であるため停止します。

削除は、バケットを特別な「tombstone」値に置き換えることによって処理されることに注意してください。この値は、要素を削除済みとしてマークしますが、線形プローブ チェーンの切断を回避します。したがって、線形プローブは、空の要素の場合でも正しく機能します。

于 2012-10-04T06:26:07.353 に答える