2

私は次のようにハッシュの概念にいくつかの理解の問題を抱えています：

キーを数値として持つハッシュテーブル（1-D配列、たとえばA [100] ）を実装したとします。単純なハッシュ関数H（Key）％Table_Sizeが1つあります。これは、ターゲットインデックスをハッシュテーブルに返します（この特定のキーに関連付けられた値にアクセスしている間）。

0（キー）をテーブルに格納したいとします。このキーをH（ハッシュ関数）に渡すと、ランダムなインデックス、たとえば25が返されます。

配列A（インデックス25）のこの場所には2つの可能性があります。

  1. A [25]には、すでに保存されている0以外のキーが含まれています（以前）
  2. A[25]には0が含まれています

最初の可能性には衝突があり、簡単に識別できます（現在のkey：0とすでに保存されているkey：kが異なるため）。したがって、最初の可能性では問題ありません。

しかし、2つ目は、衝突の有無をどうやって知ることができるでしょうか。

私が知っている限り、ハッシュテーブルまたは配列はメインメモリの一部になります。A[25]がメモリ位置500に格納されているとします。

この場所（500）が実際に空であるか、他のキーで既に埋められている天気をどのように知ることができますか？

メモリーセルのどのステータスまたは値がEMPTYまたはNULLまたはUNUSEDの場所を表しますか？

そして、衝突チェックを行ってこの場所にキーとして0を格納したい場合はどうなりますか？

現在、メモリの場所がEMPTY、NULL、またはUNUSEDの場合、RESET状態（すべてのセルが0）になると想定しています。これは本当ですか ？

ばかげた質問かもしれませんが、そのような場合の衝突をどうやってチェックするのか気になります。

-

前もって感謝します！！（ハイテイン、ハイデラバード）

4

3 に答える 3

2

ここでの考え方は、空のセルの表現を見つけなければならないということです。通常、次の 3 つがあります。

1 つ目は次のとおりです。通常は 0 または -1 の値を選択します。これは、空のセルを表すテーブルには決してないことがわかっています。次に、値がそこにある場合は、空き領域があることがわかり、そこに何かを入れることができます.

2 つ目は、ポインタの配列を使用することです: int *array[100] など。ポインターを NULL として初期化します。それらが NULL の場合、整数を割り当てて、そこを指す位置を設定できます。

3 つ目は、2 次配列を使用して、位置 i が有効な位置であるかどうかを判断することです。そのすべてを空として初期化します。誰かを配列[i]に入れるときはいつでも、有効な[i]位置を有効に設定します。

于 2012-10-26T18:12:54.430 に答える
0

これは、メモリを節約し、整数キーのすべての値を許可する提案です。

ハッシュテーブルを2つに分割し、0または1になる確率がほぼ等しいキーのビットを使用し、それを使用して、検索するハッシュテーブルの半分を選択します。キーからそのビットを削除します...キーが32ビットの場合tag、ハッシュテーブルで検索する31ビットがあります。ハッシュテーブルエントリの1ビットを使用して、空（0）または有効（1）を示します。最初はすべて0です。エントリを追加するときは、タグ（キーから半分を選択するために使用されるビットを引いたもの）を設定し、有効なビット。

于 2012-10-26T18:43:45.893 に答える
0

ハッシュ テーブルに、決して表示されないことがわかっている数値 (明らかに 0 ではなく、おそらく -1) を入力するか、または int へのポインターを使用して、空の場合は null に設定します。

于 2012-10-26T18:21:50.037 に答える