1

特定のケースの関数で大きな j の場合、以下のハッシュ関数は負の値を返します。

int hashing::hash(string a)
{
    int i = 0;
    int hvalue = 0;
    int h =0 ;
    while(a[i]!=NULL)
    {
        hvalue = hvalue + (int(a[i]))*pow(31,i);
        i++;
    }
    h = hvalue%j;
    return h;
}

そんなことがあるものか？どうすれば修正できますか？

上記のコードでは、j はファイルのサイズを使用して計算された素数です。負の値は、文字列の形式が「the s」である特定のケースで発生します。

私は何を間違っていますか？どうすれば修正できますか？

4

1 に答える 1

1

intは有限の範囲を持ち、(通常は) 符号付きの値であることを思い出してください。つまり、 の最大値を超えると、intラップアラウンドして負になる可能性があります。

これを修正するには、いくつかの方法があります。まず、 s を使用してハッシュ コードを保持するように切り替えることができunsigned intます。これは決して負ではなく、ラップ アラウンド時に適切に動作します。または、引き続きints を使用する場合は、次のようにして符号ビット (値を負にする数値の先頭にあるビット) をマスクすることができます。

return (hvalue & INT_MAX) % j;

(ここで、INT_MAXは で定義されてい<climits>ます)。これにより、値が確実に正になりますが、ハッシュ コードから少し失われるため、大きなデータ セットの場合はさらにクラスタリングが発生する可能性があります。mod の前にを実行する理由は&、mod を実行する前に値が正であることを確認するためです。そうしないと、バケットの数がオーバーフローしてしまいます。

編集：ロジックにも重大なエラーがあります。このループは正しくありません:

while(a[i]!=NULL) {
    ...
}

C++ スタイルの文字列は null で終了しないため、文字列の末尾を超えて読み取った場合に停止するとは限りません。これを read に変更してみてください

for (int i = 0; i < a.length(); i++) { 
    /* ... process a[i] ... */
}

お役に立てれば！

于 2013-10-25T22:53:14.800 に答える