6

出于性能原因，我需要将一组由字符串标识的对象分组。对象可以通过数字或前缀（限定）形式的字符串来标识，其中用点分隔标识符的各个部分：

12
323
12343
2345233
123123131
ns1:my.label.one
ns1:my.label.two
ns1:my.label.three
ns1:system.text.one
ns2:edit.box.grey
ns2:edit.box.black
ns2:edit.box.mixed

数字标识符从 1 到数百万不等。文本标识符很可能有很多以相同的名称空间前缀 (ns1:) 和相同的路径前缀 (edit.box.) 开头。

为此目的最好的散列函数是什么？如果我可以根据对象标识符统计信息以某种方式预测存储桶的大小，那就太好了。有没有一些好的文章可以根据一些统计信息构造好的散列函数？

有数百万个这样的标识符，但目的是根据散列函数将它们分成 1-2 千个组。

4

3 回答 3

3

两个好的散列函数都可以映射到相同的值空间，并且通常不会因为组合它们而导致任何新问题。

所以你的哈希函数看起来像这样：

if it's an integer value:
    return int_hash(integer value)
return string_hash(string value)

除非在某些模 N 值周围有任何整数聚集，其中 N 是可能的桶数，否则int_hash可以只返回其输入。

选择字符串散列并不是一个新问题。尝试“djb2”（http://www.cse.yorku.ca/~oz/hash.html）或类似的，除非你有淫秽的性能要求。

我认为修改散列函数以考虑公共前缀没有多大意义。如果您的哈希函数一开始就很好，那么公共前缀不太可能会创建任何哈希值聚集。

如果你这样做，并且哈希并没有意外地表现不佳，并且你将几百万个哈希值放入几千个桶中，那么桶人口将是正态分布的，具有平均值（几百万 / 几千）和方差1/12（几千）^2

每个桶平均有 1500 个条目，这使得标准偏差在 430 左右。正态分布的 95% 位于平均值的 2 个标准差内，因此 95% 的桶将包含 640-2360 个条目，除非我已经我算错了。这是否足够，或者您是否需要桶的尺寸更接近相似？

于 2009-12-14T17:17:12.333 回答
0

您可能会安全地使用sha1并将其截断为您想要的任何大小。

它不会非常有效，但也许哈希函数不会成为瓶颈？

于 2009-12-14T16:42:54.367 回答
0

我认为 CRC16 将是用于这些字符串的合理散列，并且组不应超过 1-2 千。

这应该使哈希表大约 1MB + 无论您在其中有多少项目 * 4 字节，所以我们说的是 50MB，然后您还存储了所有实际数据，最好非常小。

于 2009-12-14T16:45:43.733 回答