ハッシュテーブルを分離する - ハングテーブルについての簡単な質問

Question

ハッシュテーブルについての簡単な質問。 私は現在、 ハッシュテーブルを実装しています。 とオープンアドレッシングの組み合わせを使用し、各バケットのリンクリストの長さを特定の長さに制限しています（ ）。

しかし、私はこのハッシュテーブル構造を使って を効率的に取得/削除する方法を考えるのに苦労しており、盲目的にばかげているかどうか疑問に思っています。

私が衝突解決スキームを使用して継続的にプローブしようとすると、潜在的に永遠になり、キーがテーブルにないかどうかを決して知ることができません。これは、ほとんどのプロービング方法ではすべてのバケットがカバーされないため、線形プロービングを使用したくないからです。

ほとんどのプロービング方法はすべてのバケットをカバーするわけではないので、あなたが見たバケットを追跡するのは高価ですが、バケットが空になってもプロービングパス内の次のバケットはそうではありません空のバケツに遭遇すると停止します。

この問題に関するご意見は大変ありがとうございます。

ありがとうございます！無制限の衝突のようなシナリオでは

Answer 1

、我々は通常、使用する傾向がある：プロービング

• リニア：nは、nが素数> = 7、なぜプライムあるたびに、ジャンプ？素数を使ったhastablesの90％は、通常、テーブル内のすべてのセルを繰り返し処理するため、各セルを飛び越すのではなく、テーブル全体を移動します。
• poly probling：毎回n回ジャンプする.nはf（x）= x^2 + 2x + 1のような多項式関数を使って再計算される。これは各セルで異なる結果をもたらし、セル内の値に完全に基づいていません。