4

私のインストラクターはこれを私たちに投げかけ、ハッシュ関数の書き方をググる必要があるだけだと言いました. 私はこれについて非常に方向性がありません。クラス用の基本的なハッシュ テーブル テンプレートを作成しましたが、約 160,000 個の文字列を少なくとも 500 個のバケットを持つテーブルに並べ替える必要があるプロジェクトが予定されています (速度を上げるために、もっと多くのことをしたいと考えています)。

これに関する簡潔で簡単に消化できる情報をどこから入手すればよいかわかりません。

どんな助けでも大歓迎です。

4

1 に答える 1

5

ユニバーサル ハッシュ関数をお勧めします。この種の関数は、たとえデータが敵によって選択されたとしても、予想される少数の衝突を保証します。ユニバーサルハッシュ関数はたくさんあります。

文字列の場合は、次のハッシュ関数を採用できます。

文字cに対して#(c) cの算術値ie(ASCII)を定義します。x=c1c1...cn定義する文字列の場合ここに画像の説明を入力ここに画像の説明を入力

HSizeが整数でkが大きな素数 (ユーザーが定義) の場合、範囲 のハッシュ関数は次のようになります。0<a,b<k*HSize

ここに画像の説明を入力

この関数は、[0, HSize-1]

出力値は、ホーナーの法則によって計算され、各演算の後に除算のモジュロが求められk*HSizeます。

したがって、関数HashFunctionを作成し、ハッシュする文字列をパラメーターとして渡します。コードは次のとおりです。

#define k 7919 
#define Hsize 1009   
#define a 321
#define b 43112

long long HashFunction(string text)
{
  int i;
  long long  res = 0;
  long long M = (Hsize * k);
  cout<<"M = "<<M<<endl;
  cout<<"Hsize = "<<Hsize<<endl;
  cout<<"k = "<<k<<endl;
  int s=text.size();
  for(i = s-1; i >= 0; i--)
  {
    res = a * (res * 256 + (int)text[i]);
    //cout<<"res before modulo = "<<res<<endl;
    res=res % M;
    //cout<<"res after modulo = "<<res<<endl;
  }
    long long res1 = (res + b) / k;
    return res1;
}
于 2013-11-09T15:05:13.600 に答える