PHP整数溢出的哈希函数

Question

我查看了很多有关“PHP整数溢出”的问题，但没有找到能回答我的具体问题的答案，所以我希望我没有错过现有的答案。

我想在PHP中使用djb2哈希函数将键哈希为类似于分片标识符（SimpleDB的域索引）的东西。它会溢出无符号长整数，因此我无法在纯PHP中完全相同地执行它，因为PHP的本机整数是32位有符号的。

因此，我尝试了PHP的bc和libgmp数学扩展，它们允许任意长度，并解决了符号/比例问题，但它们使整数“太大”-即它们不会溢出。

特别是使用GMP可以正常工作并似乎给出一致的结果，但显然比C慢一个数量级（0m0.017s与0m0.002s）。我不知道这是否仅仅是因为它是PHP vs C，还是如果我能让它溢出，那么它在PHP中会显着更快。我宁愿测试并找出，但我找不到让它发生的方法。

那么，在PHP中是否有任何方法可以强制ULONG最大值？也许我需要在PHP扩展中包装C函数吗？或者，考虑到我计划仅哈希短键（可能为64个字符或更少），那么这会提供严重递减的回报吗？

- Igor Clark

---

这种有意的溢出是为了消除某些模运算的需求吗？如果是，那么位移和减法/否定的组合不能帮助吗？我在想类似于自定义二进制补码的概念。 - jon_darkstar

我之前的印象是哈希时溢出是允许/预期的，但并没有使任何东西更快。在这种情况下，所执行的操作，即位移和加法，与大小无关（或者不敏感）。因此，我认为缺少溢出对性能影响不大。PHP w/ GMP解决方案比什么慢十倍？ - jon_darkstar

你好Jon，谢谢。取模运算发生在溢出运算之后。PHP/GMP比C中相同的例程慢十倍 - 我不确定这是因为在GMP中使用了非常大的数字而不是允许溢出，还是因为在执行PHP时发生的其他事情。 - Igor Clark

Answer 1

为什么你认为这些哈希函数需要超过32位？`long`类型并不能保证是那个大小，它们只是大于等于32位。在我的32位平台上，`long`始终是32位。

我猜你链接的那些注释是在64位还不太流行的时候写的，而且也是在引入了`long long`类型（即使在32位平台上也大于等于64位）之前，所以作者只是使用了当时可用的最大类型。

那个"djb2"哈希函数只是另一种与线性同余生成器几乎类似的哈希函数变体，它已经被知道很长时间了。显式取模操作在其中被替换为溢出，实际上相当于"modulo 2^(sizeof long)"。如果编译成C代码，这对于性能可能有好处，但对于哈希质量可能就不那么好了。而且在PHP中没有意义，因为数字会被提升为`double`类型并无限增长。

我建议使用通常的PHP整数与该哈希算法，但是通过将显式模数与除数相加来改进哈希，该除数应为小于PHP_INT_MAX的质数（顺便问一下，在64位版本的PHP中有检查过这个限制吗？）也许，乘数（33）需要更改以获得必须哈希的字符串更好的哈希分布。

- Gas Welder