関数はハッシュ番号を計算しますが、正確には何を行い、なぜですか？

Question

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

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

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

    return res; 
} 

Answer 1

なぜ "RES * 31 + *キー"

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

なぜ31？

おそらく2のべき乗を避けるためには、値を左にシフトして、数回シフトした後に値を失います。 2の非累乗はこの問題を回避する。

Answer 2

実装は、D.J.による乗法的文字列ハッシュ関数の変形です。バーンスタイン：

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"の対応するレコードが格納されるテーブルの場所を私たちに与えます。ハッシュテーブルは、連想配列と動的セットを実装するために使用されます。詳細については、Wikipedia pageで始めることをお勧めします。

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