0

この関数を考えてみましょう:

unsigned hash(char *s)
{
  char *p;
  unsigned hashval;
  for(p = s; *p; p++)
    hashval = *p + 31 * hashval;
  return hashval;
}

sオーバーフローなど、間違った結果を返すバイト数を測定するにはどうすればよいですか? 私は32ビットプラットフォームを使用しています。

4

2 に答える 2

5

読むように変更すると

unsigned hash(const char *s)
{
  const unsigned char *p;
  unsigned hashval = 0;
  for (p = (const unsigned char *) s; *p; p++)
    hashval = *p + 31u * hashval;
  return hashval;
}

整数オーバーフローが原因で未定義の動作が発生する可能性はなくなりました。これは、算術に関連するすべての型が符号なしであるため、すべてが mod 2 n ( nunsignedはビット単位の幅) でラップされるためです。また、初期化されていない変数の使用を修正し、 と を作成sしましp constた。これにより、最適化が改善されたり、関数本体の間違いが検出されたりする可能性があります。

（正確な算術変換規則は今のところ覚えていません。そもそも不可能だったかもしれません。しかし、このように書くと明らかに不可能になります。）

ところで、最近知られているはるかに優れたハッシュ関数があります。そうする強い理由がない場合は、SipHashを使用することをお勧めします。

于 2013-02-15T03:12:00.373 に答える
3

いくつかの考え：

まず、ハッシュ関数ではオーバーフローが予想されます。

第 2 に、関数には が含まれており31*hashval、文字列内のすべての要素には少なくとも 1 の値が必要であるため、オーバーフローに達する前に保持できる最長の文字列はすべて \x01 の文字列であり、ハッシュをオーバーフローします。長さが 6 になると (*31操作では数値全体が左側の 5 ビットに分散されるため、キャリーが発生します。つまり、6 番目のビットに影響を与える可能性が高く、6*6 = 36 > 32 になります) ）。バイトが大きくなると、この数は少なくなります (最初のバイトが動作をほぼ定義します。これが大きいと、5 バイト後にオーバーフローが発生する可能性があります)。これは、実際のビットとバイトで示す方が簡単です。*32アルゴリズムではなく aを使用し*31ます (まったく正しくありませんが、心配するキャリーが少なくなります。アイデアが得られるでしょう):

byte      hash is less than:
0000a000  00000000 00000000 00000000 0000a000
10000000  00000000 00000000 000000a0 10000000
b0000000  00000000 00000000 a0100000 b0000000
c0000000  00000000 00a01000 00b00000 c0000000
d0000000  0000a010 0000b000 00c00000 d0000000
anything  OVERFLOW!

上で指摘したように、すべてを符号なし整数として宣言することで、(かなり貧弱な) ハッシュ アルゴリズムの予測可能な動作を改善できます。また、コンパイラがハッシュをゼロに設定すると仮定するのではなく、ハッシュを初期化することをお勧めします (ゼロ以外の値が良い考えかもしれません) (それが定義された動作であると 100% 確信しているわけではありません)。最後に、オーバーフローが気になり、警告を表示したい場合は、次のようにコードを変更します。

for(p = s; *p; p++) {
    if((hashval > 0xFFFFFFFF/31) || (*p>>1 + 31 * (hashval>>1)) > 0x7FFFFFFF) {
        printf("hash is about to overflow at character %c\n", *p);
    }
    hashval = *p + 31 * hashval;
}
于 2013-02-15T03:38:34.220 に答える