c - 为什么位移运算符使我的哈希函数如此快？

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 5 年前。

Improve this question

我现在正在学习 C，我最初为我在 CS50 edx 类(class)中构建的拼写检查程序构建了这个哈希函数。

int hashing(char *word)      
{

    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
        hash += word[i];
    return hash % HTABLE_SIZE;
}

然后我偶然发现了这个hash function在使用位移位运算符的 reddit 上。

int hashing(char *word)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
        hash = (hash << 2) ^ word[i];
    return hash % HTABLE_SIZE;
} 

使用这个哈希函数，我的程序速度从 0.13 秒缩短到 0.06 秒。有人可以向我解释一下为什么这个哈希函数这么快吗？

Answer 1

我不认为 shift + xor 比加法更快。

但是，生成的哈希表可能要快得多，因为哈希值分布得更好。