0 
int hash (const string &key, int tableSize) {
   int hashVal = 0; 

   for (int i = 0; i < key.length(); i++)
        hashVal = 37*hashVal + key[i]; 
   hashVal %= tableSize; 
   if (hashVal < 0)   /* in case overflows occurs */
        hashVal += tableSize; 

   return hashVal;      
};

hashVal がゼロより小さいかどうかを制御するのはなぜですか? これはどのように可能ですか？

4

5 に答える 5

2

文字列が十分に長い場合、コードは次のようになります。

for (int i = 0; i < key.length(); i++)
    hashVal = 37*hashVal + key[i];

hashValの値が an の最大値int(通常は 2 31 − 1 など) を超えて負になる可能性があります。これは整数オーバーフローと呼ばれます。

C++ 標準では、負のオペランドの演算子の値が正か負かを指定していません。%したがって、コンパイラと CPU アーキテクチャ (および場合によってはコンパイル時のスイッチ) に応じて、式 likeは または のいずれか-47 % 37に評価される場合があります。したがって、引用したコードは、結果が負の場合にモジュラスを結果に追加することにより、前者の可能性を防ぎます。-1027

ところで、この問題を回避する簡単な方法はhashVal、unsigned として定義することでした。

于 2012-12-30T12:38:27.177 に答える
2

変数 hashVal でオーバーフローを取得できます。これは (時々) 負の値になります。たとえば、C++ プログラムで 3 * 1000 * 1000 * 1000 の値を出力してみてください。

std::cout << 3 * 1000 * 1000 * 1000;

私のコンピューターとコンパイラーでは、これは -1294967296 を出力します。

結果の 3000000000 は 2 進数では 10110010110100000101111000000000 ですが、この特定のプラットフォームでは整数は 32 ビットであり、2 の補数法を使用して負の数を表すため、このビット パターンは負の数を表します。

標準では、整数オーバーフローは未定義の動作として定義されているため、実際には何でも発生する可能性がありますが、これは典型的な結果です。

于 2012-12-30T12:34:22.267 に答える
0

キーが十分に長い場合、hashVal値が負になることがあります。さまざまな長さの文字列 (たとえば、「1」、「11」、「111」、「1111」など) を試して、どこhashValが負になるかを確認できます (約 5 ～ 7 文字で十分です)。

次に、負の数のモジュロを取得しようとしますが、これも負になります。ただし、負の配列インデックスを指すことはできません (この関数は、文字列が格納される位置を計算するようです)。そのため、配列インデックスとして正かつ適切にします。

于 2012-12-30T12:38:37.353 に答える
0

hashValループ内で非常に高速に大きくなり、プラットフォームに依存する最大値forよりも簡単に大きくなる可能性があります。ループ後に負のsigned int場合は、演算子の後でも負になる可能性があり、これもプラットフォームに依存します (場合によっては、常に負でない値を返しますが、負を返すこともあります)、後で負かどうかを確認する必要があります。hashValfor%=hashVal

于 2012-12-30T12:41:03.417 に答える
0

次の方法でハッシュ関数を呼び出してみてください

hash("HelloHello",100);

次に、プログラムをステップ実行するか、ハッシュ関数でメッセージを出力して、ハッシュが 0 を下回るかどうかを確認します。

たとえば、forループに入れることができます

if(hashVal < 0)
{
    cout<<"OVERFLOW HAS HAPPENED\n";
    break;
}

そして、hashVal が 0 を下回っていることがわかります。

于 2012-12-30T12:45:58.220 に答える