4

我正在尝试将FNV散列算法集成到基于 PHP 的项目中，作为为各种数据（例如 URL、关键字）生成散列的要求的一部分。

我看到了 Neven Boyanov 的这个实现。他提到由于 PHP 中的算术限制，他被迫使用按位移位和加法而不是乘法。他的实现正确吗？我的知识在计算机科学领域受到某种限制，因此我无法自己验证。

我的另一个问题是关于 FNV 的不同“风味”。我看到它提供了 32 位、64 位和 128 位变体，但使用上述实现我总是得到 8 个字符的十六进制哈希（我使用 dechex() 将整数结果转换为十六进制）。

给定输入“Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin at libero mi, quis luctus massa.”，我得到以下十六进制结果：

  • （32 位偏移） 5b15c0f2
  • （64 位偏移）6ea33cb5

为什么会这样？我期待来自 64 位 FNV 的 16 个字符的十六进制结果。“风味”是否仅指将使用的算术运算和种子类型而不是结果的长度？（即如果我说 64 位 FNV，散列函数将使用 64 位操作和种子，但结果仍然是 32 位）

一点启发将不胜感激:)

4

2 回答 2

2

我很早以前就写过PHP FNV哈希函数，它是为了一个特定的目的，所以当时32位的实现就足够了。

要回答您的第一个问题 - 通过比较算法（代码）和示例结果，针对其他（C 和 C++）实现对实现进行了测试。因此，对于 32 位结果，它可以正常工作。

如果您想自己实现 64 位（或 128 位）版本，您应该首先更改 FNV_offset_basis 以及第 73 行的表达式，目前是：

$hash += ($hash<<1) + ($hash<<4) + ($hash<<7) + ($hash<<8) + ($hash<<24);

...这相当于乘以二进制数为 1000000000000000110010011 的数字 16777619 (FNV_prime_32) - 分解为以下表达式：2^24 + 2^8 + 2^7 + 2^4 + 2^1 + 2^0。

对于 64 位，您应该乘以 1099511628211 - 二进制 100000000000000000000000000000000110110011 ... 表达式：2^88 + 2^8 + 2^7 + 2^5 + 2^4 + 2^1 + 2^0。

我不知道$hash << 88PHP 将如何处理表达式，但您应该自己试验一下。在我的 PHP 5.2.x 上，它不适用于大于 31 的数字。

最后，您可能需要修改$hash = $hash & 0x0ffffffff;以从结果中删除一些垃圾。我通过实验发现了这一点。对于 64 位 ot 应该是$hash = $hash & 0x0ffffffffffffffff;. 验证它是否与 PHP 一起正常工作。

您还可以使用其他 PHP 库来获得更高的算术精度。在我看来，使用按位移位更快。

事实上，您可以为任意位数生成 FNV 哈希。

于 2012-06-20T07:35:58.860 回答
0

事实证明，我引用的实现仅适用于 32 位 FNV1。我设法编译了 FNV 的C 源代码，并使用二进制文件和 Tom 建议的工具来验证 64 位 FNV 确实返回 16 个字符的十六进制哈希

于 2012-06-12T05:45:10.363 回答