djb2哈希搭配ulong使用为何能生成超32位值？32位long如何存储大数值

问题解答 #

首先给出djb2哈希算法实现代码：

unsigned long hash(char *str) 
{
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash % NUM_BUCKETS;
}

核心原理说明

• C语言标准明确规定：无符号整数的算术运算天然执行模2^N操作，其中N为该类型的比特位数，该行为是明确定义的，不存在未定义的溢出问题。32位unsigned long的N为32，可表示的最大值为2^32 - 1 = 4294967295，当运算结果超过这个值时，会自动截断高位，仅保留低32位的有效值，等价于自动对2^32取模。
• djb2算法设计时就兼容了这个特性：长字符串计算过程中产生的超大数值不需要完整存储，自动截断保留的低32位已经包含了足够的字符串特征，完全满足哈希计算的分布要求。
• 最终返回的hash % NUM_BUCKETS结果不会受中间截断影响：根据模运算的分配律，(a * b + c) mod M和(((a mod 2^32) * b + c) mod M的计算结果完全一致，中间的自动取模操作不会影响哈希值映射到哈希桶的正确性。

内容的提问来源于stack exchange，提问作者Richard