ハッシュ関数アルゴリズムのアドバイスが必要です

Question

私は、指定された文字列にその文字列をキーにマッピングすることによって "ID"を与えるハッシュ関数に取り組んでいます。私が使用する必要があるアルゴリズムは以下に記載されています

文字列 NOTE考える

• 、我々は例えば、それぞれの文字に値を割り当てる：

  N = 14, O =15, T = 20, E = 5 
  

• その後、我々は乗算と加算：

  14 * 32^3 + 15 * 32^2 + 20 * 32^1 + 5 * 32^0 
  

• この式を因数分解すると、

  ((14 * 32 + 15) * 32 + 20) * 32 + 5 
  

しかし、その値が大きすぎるかもしれませんが、私たちのような括弧の各セットの後にMOD除算を使用します。

((14 * 32 + 15)%tableSize *32 + 20)%tableSize * 32 + 5 

がどのように私はこれを達成するためのアルゴリズムを作成することができますか？私はそれをしようとしましたが、私の実装は非常に非効率的です。私の教授は、それは7行を超えてはならないと言った。誰も上記のアルゴリズムを効率的に実装する方法に関する提案を提供できますか？誰もが気に場合

私のアルゴリズムは次のとおりです。

int HashDictionary::getKey(string word) const{ 
    int wordLength = word.length(); 
    int* values = new int[wordLength]; 
    for (int i = 0; i < wordLength; i++) { 
     values[i] = int(word[i]); 
    } 

    int productSoFar = 0; 
    for(int i = 0; i < wordLength;i++){ 
     productSoFar *= 32; 

     if(i == 0){ 
      productSoFar = values[i] * 32; 
      productSoFar = productSoFar + values[i+1]; 
      productSoFar %= tableSize; 
      i++; 
     } 
     else{ 
      productSoFar += values[i]; 
      productSoFar %= tableSize; 
     } 

    } 
    delete [] values; 
    return productSoFar; 
} 

Answer 1

あなたは2つのループを必要はありません。最初に行うのは、文字を整数に変換することだけですから、必要に応じてそれぞれを変換し、値配列を完全に避けることができます。それは物事をスピードアップし、行数を減らすはずです。

Answer 2

これを試してみてください：

int HashDictionary::getKey(string word) const{ 
    int wordLength = word.length(); 
    int* values = new int[wordLength]; 
    values[0] = int(word[0]); 
    values[1] = int(word[1]); 

    int productSoFar = 0; 
    productSoFar = values[0] * 32; 
    productSoFar = productSoFar + values[1]; 
    productSoFar %= tableSize; 

    for(int i = 1; i < wordLength;i++){ 
     productSoFar *= 32; 
     productSoFar += values[i]; 
     productSoFar %= tableSize; 
     values[i] = int(word[i]); 
     } 
    delete [] values; 
    return productSoFar; 
}