适当的哈希函数用于哈希随机二进制字符串。

Question

我有两个数组：char data1[length]，其中length是8的倍数，即length可以是8、16、24...。该数组包含从以二进制模式打开的文件中读取的二进制数据。我将继续从文件中读取，并每次读取时将读取的值存储在哈希表中。这些二进制数据的分布具有随机分布。我想对每个数组进行哈希处理，并将它们存储在哈希表中，以便能够再次查找具有特定数据的char。要完成此任务，哪种哈希函数比较好呢？谢谢。

请注意，我是用C++和C编写的，因此提供任何语言的解决方案都很好。

- Mike G

---

为什么不直接使用Berkeley DB4并让该库处理所有细节呢？ - Roland Illig

你会如何处理哈希冲突？ - Jim Mischel

Answer 1

如果你读取的数据长度为8字节且分布随机，而你的哈希码需要32位，那么可以这样做：

uint32_t hashcode(const unsigned char *data) {
  uint32_t hash = 0;
  hash ^= get_uint32_le(data + 0);
  hash ^= get_uint32_le(data + 4);
  return hash;
}

uint32_t get_uint32_le(const unsigned char *data) {
  uint32_t value = 0;
  value |= data[0] << 0;
  value |= data[1] << 8;
  value |= data[2] << 16;
  value |= data[3] << 24;
  return value;
}

如果你需要更快的速度，只要你能保证data始终被正确地对齐以被解释为const uint32_t *，那么这段代码可能可以显著提高速度。

- Roland Illig

---

如问题所述，长度是8的倍数。我该如何将您的想法扩展到8的倍数而不仅仅是8字节？ - Mike G

通过向哈希码函数添加 size_t datalen 参数。当你理解了代码后，这是一件微不足道的事情。我甚至编写了代码，使其可以轻松扩展。 - Roland Illig

+1：尽管如果数据真正随机（我认为我们这里的确意思是“均匀的”），你甚至不需要使用xor；只需使用前32位作为哈希值即可。 - Oliver Charlesworth

这个方法似乎会改变数据，即使你在里面用了 const。我尝试了一下，但它仍然不停地更改我的数据。 - Mike G

我有所怀疑。代码明显只有读取操作，并且我没有使用任何强制类型转换来取消 const。我改变的唯一是局部变量。如果你能证明数据确实已经改变，我会非常感兴趣。 - Roland Illig

Answer 2

我曾成功地在我的一个项目中使用MurmurHash3。

优点：

• 它非常快，非常快。
• 它据称具有低碰撞率。

缺点：

• 它不适用于加密应用程序。
• 它没有任何形式的标准化。
• 它无法在非x86平台上移植。然而，它非常小，如果您真的需要，应该能够将其移植到Java中——虽然那并不完全相同。

对于快速哈希表实现等方面，这是一个不错的选择...

- thkala

---

我也想在我的项目中实现这个功能，实际上我想通过MurmurHash将字符串哈希成二进制。但是Murmur哈希算法也会生成负哈希值，所以我遇到了问题。我按照你上面提到的代码实现了相同的代码。如果您有任何哈希算法可以为类似的消息提供类似的哈希值，例如只更改一个字符，则哈希值的变化较小。 - MrYo