混合数字和文字识别最佳的散列函数

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条目，除非我做我的资金是错误的。那是足够的，或者你需要的水桶要更加紧密地相似尺寸的？

Answer 2

您可能会是安全与sha1去，并截断任何你想要的大小。

它不会是非常有效的，但也许是散列函数将不会是一个瓶颈？

Answer 3

我觉得CRC16将是一个合理的散列对这些字符串使用，该组织不应该去任何大于1-2万。

这应该使哈希表1MB左右+你在它* 4个字节具有然而，许多物品，所以我们谈论50MB，然后你还可以存储所有的实际数据，其中最好是非常小的。