1

3種類のプロービングを使用して、プロジェクトのハッシュテーブルを実装しています。現在、リニアに取り組んでいます。

線形プロービングについては、プロービングがどのように機能するかを理解しており、私のインストラクターは、ステップサイズを1にしたいとほのめかしました。つまり、重複は許可されていません。ですから、値を挿入する前に、値を「検索」する必要がありますよね？しかし、すべてのセルが「占有」または「削除」されるまでテーブルが使用された場合はどうなるでしょうか。次に、特定のキーを検索してそのキーがテーブルにないことを確認するには、テーブル全体を検索する必要があります。つまり、検索操作（ひいては挿入操作）はO（n）です。

それは正しくないようで、私は何かを誤解したと思います。

テーブルは少なくとも半分空である必要があり、決定された数の要素のみをプローブするため、2次プローブで同じ問題に遭遇する必要はないことを私は知っています。また、ダブルハッシュの場合、挿入するキーが存在しないことを証明するためにテーブルを検索する必要があるため、これがどのように機能するかはわかりません。しかし、どのセルも「占有されていない」場合に検索を停止する方法をどのように知ることができますか？

したがって、過去にテーブル内のすべてのエントリが占有されていたオープンハッシュでは、要素を検索するためにO（n）プローブが必要ですか（重複が許可されていない場合は挿入します）？

4

1 に答える 1

2

線形プロービングのこの側面を誤解している場合は、私もそうです。ハッシュテーブルがほぼいっぱいになると、挿入ごとにパフォーマンスがO（n）に向かって低下することに同意します。詳細については、 DonKnuthの1963年の分析を参照してください。

括弧内に、この問題の最初の分析が実際に1913年に数学者Ramanujanによって行われたことを見て驚いた。その結果は、「完全な線形プロービングハッシュテーブルの要素の総変位、つまり構築コストを意味している。約N^（3/2）です。」（ここを参照）

ただし、実際には、挿入が遅いという問題は、ほぼ満杯のハッシュテーブルでの重要な問題ではないと思います。重要な問題は、別の挿入がまったくできない状態になることです。

したがって、ハッシュテーブルの実際の実装には、理論または実験に基づいて選択されたサイズ変更に最適な負荷率を使用して、特定の負荷率を超えたときにハッシュテーブルのサイズを変更する戦略が必要です。線形ハッシュのパフォーマンスは、クラスターを回避する方法でハッシュテーブル全体にアイテムを均等に分散するハッシュ関数の機能に非常に敏感である可能性があるため、実験を使用することは特に価値があります。これにより、パフォーマンスはテーブルに挿入されるアイテム。

于 2013-03-09T20:04:34.217 に答える