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

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到数百万.文本标识符最有可能以相同的名称空间前缀(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）或类似的，除非你有令人讨厌的性能要求。

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

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

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