1

ハッシュ関数の設計を理解できていません。私は例を経験していました。関数のコメントでわかるように、乗算する数値として 31 を選択する必要があるのはなぜですか。どのように決定しますか？それは偶然ですか、それとも何か意味がありますか？

unsigned int hash(hash_table_t *hashtable, char *str)
{
    unsigned int hashval;

    /* we start our hash out at 0 */
    hashval = 0;

    /* for each character, we multiply the old hash by 31 and add the current
     * character.  Remember that shifting a number left is equivalent to 
     * multiplying it by 2 raised to the number of places shifted.  So we 
     * are in effect multiplying hashval by 32 and then subtracting hashval.  
     * Why do we do this?  Because shifting and subtraction are much more 
     * efficient operations than multiplication.
     */
    for(; *str != '\0'; str++) hashval = *str + (hashval << 5) - hashval;

    /* we then return the hash value mod the hashtable size so that it will
     * fit into the necessary range
     */
    return hashval % hashtable->size;
}
4

2 に答える 2

3

問題のハッシュは、Bernstein Hash、Torek Hash、または単に「times 33」ハッシュとして知られています。その単純さ、速度、および英語の文字列データを適切に配布できるため、非常に人気があります。

あなたのコメントは、実際には31を掛けていることに注意してください。これは、あなたには恣意的に見え、実際には少し恣意的です。Apache Portable Runtime のハッシュ アルゴリズム ソースには、多くの可能な定数が適切に機能するというコメントがあります (33 が最も一般的です)。それらはすべて奇数で、2 の累乗に近い値です。つまり、シフトと加算または減算にうまく変換されます。

ハッシュを理解するのに役立つその他のリソース:

于 2012-01-21T00:22:26.487 に答える
1

65kビューのハッシュ関数の講義です。YouTube: http://www.youtube.com/watch?v=KW0UvOW0XIo

これはまさにあなたが求めているものではありませんが、あなたの質問は、ハッシュに関する知識が限られていることを明らかにしています. チュートリアルを読むか、プレゼンテーションを確認することをお勧めします。

于 2012-01-20T23:40:08.060 に答える