为什么可以直接乘以33，为什么要使用位运算符来实现Djb2哈希函数，这是由Dan Bernstein提出的问题？

Question

在 Dan Bernstein 著名的 Djb2 哈希函数中，我们看到它使用位运算符而不是简单乘法。为什么要使用位运算符？它是否更快？ (hash << 5) + hash = hash * 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;
}

- zakissimo

---

欢迎来到 Stack Overflow。https://softwareengineering.stackexchange.com/questions/234967/speeds-of-multiplication-and-division 这个链接是否回答了你的问题？ - Karl Knechtel

你可能想要检查一下你的优化汇编输出，因为如果在这种情况下，两个版本的计算最终生成相同的函数代码，我一点也不会感到惊讶。无论你是按照所示代码明确指定还是只使用（哈希值*33），clang 12.01和gcc 11.2都将生成一个左移算术位5，以及随后的加法。 - WhozCraig

任何现代编译器都会为两者生成相同的代码（godbolt确认），但当这个算法在1991年设计时可能并非如此。 - that other guy

Answer 1

为什么我们可以直接乘以33，还要使用位运算符呢？但是相对于简单的乘法，为什么要使用它？它更快吗？

根据BITD，编译器不像现在这么聪明，所以通常会更快。@that other guy 今天，除非你的情况证明需要（例如使用弱编译器），否则代码应该清晰易懂。一个好的编译器无论哪种方式都会生成高效的代码。

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);
}

- chux - Reinstate Monica