7

次のような文字列のハッシュキーを生成するためにdjb2アルゴリズムを使用しています

hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

これで、すべてのループで 2 つの大きな数の乗算が行われます。しばらくすると、文字列の 5 番目の文字の 4 番目の文字で、ハッシュ値が巨大になるため、オーバーフローが発生します。

ハッシュ値がオーバーフローせず、ハッシュも正しく行われるようにリファクタリングする正しい方法は何ですか?

4

4 に答える 4

20

ハッシュ計算はしばしばオーバーフローします。オーバーフローしたときに何が起こるかについて保証がある限り、それは一般的にまったく問題ではありません。ハッシュのポイントは、大きさなどの点で何かを意味する数値を持つことではないことを忘れないでください-それは単に等しいことを検出する方法です. なぜオーバーフローがそれを妨げるのでしょうか?

于 2010-04-03T15:38:01.027 に答える
4

静的/ランタイムアナライザーを使用して整数のオーバーフローについて警告することを考えていますか？これは、警告を無視できるケースの1つです。ハッシュ関数は特定のタイプのプロパティ用に設計されているため、アナライザーからの警告について心配する必要はありません。自分でハッシュ関数を作成しようとしないでください。

于 2010-04-03T16:29:42.463 に答える
4

あなたはそれをすべきではありません。モジュロがないため、整数オーバーフローは関数の予期される動作です (そして、それを念頭に置いて設計されています)。なぜ変更したいのですか？

于 2010-04-03T15:39:00.133 に答える
1

リターン (ハッシュ & 0xFFFFFFFF); // または、必要なマスクは、一貫性を保つ限り重要ではありません。

于 2012-02-02T19:02:24.780 に答える