algorithm - 混合数字和文字标识符的最佳哈希函数

Question

出于性能原因，我需要将一组由字符串标识的对象分成组。对象可以由数字或前缀(限定)形式的字符串标识，并用点分隔标识符的各个部分:

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 到几百万。文本标识符很可能有很多以相同的 namespace 前缀 (ns1:) 和相同的路径前缀 (edit.box.) 开头。

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

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

Answer 1

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

所以你的哈希函数可以是这样的:

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)或类似的，除非你有淫秽的性能要求。

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

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

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