0

ここに画像の説明を入力

誰でもこの問題を開始する方法を知っていますか? つまり、ハッシュの機能は理解していますが、この質問が何について話しているのかわかりません。

これをどうやって進めるかについてのアイデアはありますか？

与えられた:

  • ハッシュ関数: h(x) = | 2x + 5 | mod M
  • 容量 N のバケット配列
  • キーを持つオブジェクトのセット: 12、44、13、88、23、94、11、39、20、16、5 (左から右に入力するため)

4.a * [5 pts]***** M=N=11 で衝突が別のチェーンを使用して処理されるハッシュ テーブルを記述します。

4.b * [5 pts]***** M=N=11 のハッシュ テーブルを作成し、線形プローブを使用して衝突を処理します。

4.c * [5 pts]***** M=11 の場合、これらのキーをハッシュして衝突を発生させない N の値を見つけることができますか?

4

3 に答える 3

1

方程式 h(x) を使用して、各キーのハッシュ値を見つけます。これは、値が格納される配列内の場所です。これは明らかに宿題なので、線形プロービング、分離チェーン、または 4c については説明しません。

M は、値を入れる配列のサイズです。

N は、ハッシュしているオブジェクトの数です。

于 2012-12-07T23:35:55.193 に答える
1
  • 数値 (x) を指定して、テーブル内のどこに移動するかを決定する関数があります。
  • テーブルのサイズは N です。この質問の a と b の部分の場合、N は 11 です。
  • M は、質問 a、b、および c で 11 です。M は、与えられた式に差し込まれる単なる値ですh(x) = (2x + 5) mod M
  • したがって、数値が 12 の場合、h(12) = (2 * 12 + 5) mod 11=> 7 です。したがって、最初の結果はバケット 7 に入ります。
  • 次に、残りの数値を順番に調べて、それぞれの h(x) を計算します。
  • ただし、競合が発生した場合 (つまり、番号が入るはずのバケットが前の番号によって既に満たされているシナリオ)、別のバケットを選択する必要があります。どちらを選択するかは、オーバーフロー戦略によって異なります。
  • 問題のオーバーフロー戦略は別の連鎖です
  • 質問Bでは、オーバーフロー戦略は線形プローブです
  • これらの方法に慣れていない場合は、以下をご覧ください。
  • C が読み取りとして取得される場合、最初の衝突に達するまで、リストの先頭から番号を取得することを意味すると思います。ただし、バケットに既にある数が N の値です。
  • ただし、質問 CI が信じているのは誤植だと思います。指定された数値のリストをすべて一意のバケットに割り当てることができるようにする M の値を見つける必要があると思います (つまり、衝突なし/オーバーフロー戦略なし)。
于 2012-12-07T23:51:09.557 に答える
0

各キーのハッシュを計算することから始めます。

于 2012-12-07T23:35:43.507 に答える