問題タブ [linear-probing]

線形プローブを使用してハッシュテーブルを実装しようとしています。

(キー、値) のペアをハッシュテーブルに挿入する前に、それが半分埋まっているかどうかを確認したいと思います。そうであれば、基になる配列のサイズを 2 倍にする必要があります。

明らかに、それを行うには2つの方法があります。

1 つは、2 倍のサイズの別の配列を作成し、古い配列のすべてのエントリを再ハッシュして、それらを新しい配列に追加することです。次に、古い配列を新しい配列に再バインドします。この方法は実装が簡単ですが、多くのスペースを使用します。

もう 1 つは、配列を 2 倍にして、その場で再ハッシュを行うことです。再ハッシュすると、新しくハッシュされたスロットと古いスロットの両方と衝突が発生する可能性があるため、この方法では実行時間が長くなる可能性があるようです。

どの方法を使用すればよいですか?

だから私は8バケットのハッシュテーブルを持っていますh(i) = i mod 8 これらは挿入されている数字です:

ハッシュテーブルの学習を始めたばかりなので、これらの概念についてかなり混乱しています。

開いているハッシュ テーブルがある場合、結果は次のようになります。

閉じたハッシュを使用して線形衝突処理を実装する必要がある場合、

私はこれを正しく行っていますか？

Pythonが辞書を実装する方法を研究しています。Python 辞書実装の方程式の 1 つは、次の方程式を使用して、空の辞書スロットの疑似ランダム プローブを関連付けます。

ここで説明されています。

この質問を読みました。Python の組み込み辞書はどのように実装されていますか? 、基本的に辞書がどのように実装されているかを理解しています。

私が理解していないのは、方程式の理由/方法です:

の残りのすべてを循環します 2**i。たとえばi = 3、合計開始サイズが 8 の 場合j、次のサイクルが実行されます。

開始サイズが 16 の場合、次のサイクルを実行します。

これは、ディクショナリ内のすべてのスロットをプローブするのに非常に役立ちます。 しかし、なぜそれが機能するのですか? なぜ機能 するのに機能しj = ((j*5)+1)ないのか、j = ((j*6)+1) またはj = ((j*3)+1) その両方が小さなサイクルで立ち往生するのか.

方程式が機能するだけでなく、これをより直感的に理解できることを望んでおり、それが彼らがそれを使用した理由です。

線形プローブによって独自のハッシュ テーブルを実装することになっていますが、削除機能に問題があります。正しく動作しませんが、問題を特定できません:

私のデバッガーはこれを出力として表示するため、明らかに私の方法にはテーブルのギャップに関する問題があります。

助けてくれてありがとう！

C ++でハッシュテーブルの線形プローブを実装したかったのですが、キーと値のペアは次のようなジェネリック型になります: vector< ペア< キー、値> > (キー、値はジェネリック型です)。

ここで、セルが占有されている場合の線形プローブでは、空のセルが見つかるまでベクトルをトラバースし、そのセルに新しいペアを配置します。

問題は、ジェネリック型では、特定のセルが占有されているかどうかをどのように確認できるかということです。これらの条件は使用できません:

また

では、ベクトル内の特定のセルが空かどうかを確認するにはどうすればよいでしょうか? コンセプトを誤解していた場合は、訂正してください。

goでハッシュプログラムを実装しようとしています.挿入を行い、線形プローブを使用して衝突を解決しました. 値を取り戻そうとすると、線形プローブを使用して衝突を修正したため、異なる値を取得しています。

これは私のプログラムです: https://play.golang.org/p/7Pmqu6A313