将DJB Hash转换为64位

Question

如果我使用64位无符号整数,Dan Bernstein的哈希函数是否仍能正常运行？

uint64
hash_djb2(register uchar *str, register size_t length) {
    register uint64 hash = 5381L;
    while (length--) {
        hash = ((hash << 5L) + hash) + *str++; /* hash * 33 + c */
    }
    return hash;
}

Answer 1

djb散列函数基于线性同余生成器,其形式为x =(a·x + c)mod m.

通过检查函数,我们意识到a = 33,c = input在djb的情况下,模数有点隐藏,因为它是由变量hash的类型表示的,unsigned long是原始形式,包含32位数据.当值超出无符号长整数的值时,它会溢出并继续,因此模数为2 ^ 32.

根据Knuth在他的"计算机程序设计的艺术"第2卷:第3.2.1章的数值算法中,m必须能被(a-1)的所有素因子整除,以使线性同余生成器具有最大周期(周期=模数) )(以及伯恩斯坦先生已经考虑的其他事实).由于m = 2^64没有引入新的素因子,因为根据定义2是两者的素数,2^32并且2^64满足该规则.

然后,使用这种新的哈希算法,您可以获得与模数一样长的句点,这意味着您将覆盖64位整数的所有可能值.

请记住,虽然改变算法的任何数学值都不能轻易做到.需要一个全新的统计分析来充分了解新算法的缺陷和好处,即使您只更改了它的一个变量.您不能简单地更改值,并希望获得与原始线性同余生成器相同的功能.前一算法不保留熵和碰撞等统计特征.然后你不能声称已经实现了djb算法,既没有引用djb的任何统计性能来证明你的实现有什么.