Dan Bernstein 的 Djb2 哈希函数：当我们只能乘以 33 时，为什么要使用按位运算符？

Question

在 Dan Bernstein 著名的 Djb2 哈希函数中，我发现最好使用按位运算符，但为什么要使用它而不是简单的乘法呢？是不是更快了？

(散列 << 5) + 散列 = 散列 * 33

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Djb2 hash function by Dan Bernstein
    unsigned long hash = 5381;
    int c;
    while ((c = *word++))
    {
        hash = ((hash << 5) + hash) + tolower(c); /* hash * 33 + c */
    }

    return hash % N;
}

Answer 1

Why use bitwise operator when we can just multiply by 33?
but why use it over a simple multiplication ? Is it faster ?

BITD, compilers were not as smart and so it was often faster.

今天，为了清晰起见，编写代码，除非您的情况另有说明（例如，使用弱编译器）。无论哪种方式，一个好的编译器都会发出高效的代码。

hash = ((hash << 5) + hash) + tolower(c);
// or
hash = hash * 33u + tolower(c);

因为这是一个散列，所以两者都一样清楚。

迂腐

如果c < 0，islower()就不是那么好定义了。

替代方案，使用一些转换来消除迂腐的警告，并且可能更快一点未签名代码。

unsigned hash(const char *word) {
    const unsigned char *uword = (const unsigned char *) word;
    unsigned long hash = 5381u;
    int c;
    while ((c = *uword++)) 
        hash = hash*33u + (unsigned)tolower(c);
    }
    return (unsigned) (hash % N);
}

Dan Bernstein 的 Djb2 哈希函数：当我们只能乘以 33 时，为什么要使用按位运算符？

Djb2 hash function by Dan Bernstein : Why use bitwise operator when we can just multiply by 33?

c

hash

bit-manipulation