2

描述

我有一组相当大的（字符串，字符串，字符串）唯一元组（大约 4000 万，但可以变得更大）。对于每个元组，我计算一个无符号整数值。我想将这些值存储在某个地方，以便在生成它们之后可以重用它们（即使在应用程序出现故障之后，内存存储也是不可能的，不幸的是数据库也是如此）。

起初，我将它们作为元组（字符串、字符串、字符串、值）存储在一个文件中，但读取 4000 万条记录需要时间（而且我几乎立即需要它）。

我决定首先计算每个 (string, string, string) 元组的哈希值，然后将其标准化为 [0, n] （其中n是值的数量）并仅将值以排序顺序存储在二进制文件中（按标准化哈希值排序）。之后，我可以简单地 mmap() 这个文件并使用 mmap[normalize(hash(string, string, string))] 获取值。

我的哈希函数非常简单但速度很快，适用于我的情况（没有注意到任何冲突）：

concatenatedString = s1+"."+s2+"."+s3
unsigned int hash = 31;
for(int i = 0; i < concatenatedString.length(); i++) {
  hash = hash * 101 + (unsigned int) concatenatedString[i];
}

与归一化相同（直截了当）：

((long) n * hash) / max_value

n - 我的归一化范围的上限（所以大约 4000 万，我取 n 不是 (n - lower_bound) 因为 lowe_bound = 0）

max_value - 旧集合的最大值（在我的情况下为 UINT_MAX，min_value = 0 所以我不将它包含在等式中）

问题

我的哈希函数不会产生 0 到 4,294,967,295（无符号整数）范围内的均匀分布的值（看不出它是如何做到的）。因此，在规范化之后，我有很多冲突导致数据丢失（覆盖相同数组索引下的值）。

有没有什么聪明的方法可以做我想做的事但没有那些冲突？

我完全知道可能会发生一些碰撞。问题是我的方法往往过于频繁地发生。我的散列范围比我的元素数量大 100 倍，所以我猜可能有办法做到这一点，但我还没有弄清楚怎么做。

解决方案 最后我将哈希更改为 Murmurhash，将我的规范化方法更改为简单的“模 newRange”并更改文件的格式（我现在存储所有数据（字符串字符串值）） - 文件现在很大但多亏了这一点，我才能够实现一个简单的碰撞检测机制（双散列）。

4

4 回答 4

4

实际上，我很惊讶在规范化哈希值范围之前没有发生冲突。看起来您正在使用 [0,2^32) 的非标准化范围。在这里查看生日问题图表，与 4*10^7 元素发生碰撞的概率应该高于 75%。在任何情况下，将散列输出归一化到等于元素集大小的范围实际上可以保证不平凡的冲突数量。除非您愿意为您的哈希值使用计数器，否则我看不出您将如何避免这种情况。

编辑：看到你的编辑。即使范围是元素数量的 100 倍（大约 4*10*9），您仍然可能会遇到很多冲突。如上所述，一次或多次碰撞的概率远远超过 75%。

我建议有两点：

选择不同的哈希函数

正如您所指出的，虽然您的哈希函数很快，但它不会在 [0,2^32) 范围内随机分布值。有几个散列函数既快又能更好地在散列函数范围内分配散列值。我过去使用过的一个是MurmurHash。

使用更大的范围

使用更大的范围应该可以降低碰撞的风险。再次查看这里的图表，看起来 64 位应该足以将碰撞风险降低到 10^-6 以下。在这种情况下，MurmurHash64A 和 MurmurHash64B 变体将很有用。

于 2013-02-20T07:33:49.013 回答
1

并非总是可以将散列标准化为唯一的 [0..n] 值。

我可以向您建议 2 种方法：

  1. 对文件进行排序并使用二进制搜索而不是地图。（LogN 复杂度）
  2. 用索引创建第二个文件并在 [0..5n] 范围内实现哈希表（5n 可能被任何其他数字更改，大于 n）。
于 2013-02-20T06:53:11.383 回答
1

您是说您正在使用它进行标准化：

((unsigned int) n * hash) / max_value

你说那max_value是UINT_MAX：

“max_value - 旧集的最大值（UINT_MAX”

hash并被声明unsigned int为。

好吧，你知道，那么上面只能产生值 0 和 1，这保证了碰撞。

你知道C++ 中整数和浮点除法的区别吗？

如果没有，那么我建议获取C++ 教科书。

顺便说一句，像“(unsigned int) blah”这样的强制转换是创建错误的可靠方法。他们告诉编译器闭嘴，不要告诉你可能的问题，因为，你告诉它，你知道得更多。但你没有。

于 2013-02-20T08:03:01.287 回答
0

据我了解，您需要一个唯一的哈希（这实际上是不可能的:)）：

在 Java 中 String.hashCode() 给你一个 32 位的哈希码。

如果你想要（比如说）一个 64 位的哈希码，你可以自己轻松地实现它。

如果您想要字符串的加密哈希，Java 加密库包括 MD5、SHA-1 等的实现。您通常需要将字符串转换为字节数组，然后将其提供给哈希生成器/摘要生成器。例如，请参阅@Boris Pavlović 的回答。

如果你想要一个唯一的哈希码，那你就不走运了。哈希和哈希码是非唯一的。

一个长度为 N 的 Java 字符串有 65536 ^ N 个可能的状态，并且需要一个 16 * N 位的整数来表示所有可能的值。如果你写了一个哈希函数，它产生的整数范围更小（例如小于 16 * N 位），你最终会发现多个 String 哈希到同一个整数的情况；即哈希码不能是唯一的。这被称为鸽巢原理，并且有一个直接的数学证明。（你不能打数学赢！）

于 2013-02-20T07:53:36.167 回答