5

この関数がハッシュ番号で何かをしていることは知っていますが、この関数の目的を正確に理解していませんか? なぜ "res *31 + *key" なのですか? なぜ31？

unsigned int HashAlg(char* key)
{
    unsigned int res = 0;

    while (*key != 0)
    {
        res = res * 31 + *key;
        ++key;
    }

    return res;
}
4

2 に答える 2

5

実装は、DJ Bernstein による乗法文字列ハッシュ関数のバリエーションです。

unsigned djb_hash ( void *key, int len )
{
  unsigned char *p = key;
  unsigned h = 0;
  int i;

  for ( i = 0; i < len; i++ )
    h = 33 * h + p[i];

  return h;
}

このようなハッシュ関数の目的は、文字列などの検索キーを"item1"、ハッシュ テーブルやキャッシュなどで使用できるインデックスにマップすることです。簡単に言えば、ハッシュ値は、対応するレコードを格納するテーブル内の場所を示します"item1"。ハッシュ テーブルは、連想配列と動的セットを実装するために使用されます。詳細については、ウィキペディアのページから始めることをお勧めします。

33実装では、定数が切り替えられていることがわかります31. 素数とハッシュ関数の関係を明確に証明できる実際の数学的作業はあまりありません。ハッシュ関数で素数を使用する基本的な概念は、ハッシュ関数の現在の状態を変換するという概念を中心に展開します (ハッシュ値に乗算や加算などの何らかの形式の数学演算を適用します)。結果は、統計的により高いエントロピー値、つまり新しいハッシュ値のビットのビットバイアスが非常に低い新しいハッシュ値になるように制約されます。簡単に言えば、一連の乱数に素数を掛けると、結果の数値 (ビット レベルで分析した場合) は、1 つの状態または別の状態に偏っていないはずです。つまり、P(Bi = 1) ~= 0.5. これが事実であるか、素数でのみ発生するという具体的な証拠はありません。それは、私たちが従う義務があると思われる進行中の自己宣言された直感のようです. これらのプロパティは事後的に判断されます。つまり、選択した定数を使用してハッシュ関数 (または PRNG) プロパティを分析し、定数が「うまく機能する」という直感を開発しようとします。つまり、特定の分布を生成するか、なだれ効果を実証し、一様な分布を生成します。特定の入力セットなど

于 2013-03-19T12:02:37.960 に答える
0

なぜ "res *31 + *key" なのか

だけだったらどうなるか考えてみてくださいres = res + *key。ハッシュはキーのすべての値を合計するだけです。これにより、hello、elloh、olleh、loleh などの置換された文字列に対して同じハッシュが生成されます。値 > 1 で乗算すると、この可能性ははるかに低くなります。

なぜ31？

おそらく、単純に値を左にシフトし、数シフト後にそれを失う 2 の累乗を避けるためです。2 の累乗でない場合、この問題は回避されます。

于 2013-03-19T12:01:15.937 に答える