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

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

所以散列函数可以如下所示:

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 )或者类似的,除非你有淫秽的表演要求。

我不认为修改hash函数来考虑常见的前缀有多大意义。如果您的散列函数是一个很好的开头,那么一般的前缀不太可能创建任何散列值的聚集。

如果您这样做,并且散列不会意外地表现糟糕,并且您将数百万散列值放入几千个bucket中,那么bucket总体将正常分布,平均值(几百万/几千)和方差1/12(几千)^2

平均每个桶有1500个条目,这使得标准偏差在430左右。正态分布的95%在平均值的2个标准差内,所以95%的桶将包含640-2360个条目,除非我做了错误的计算。这足够吗,或者你需要更接近相似大小的水桶吗?

你跟我一起去很安全 sha1 截短到你想要的大小。

它不会非常有效,但哈希函数可能不会成为瓶颈?

我认为在这些字符串上使用CRC16是一个合理的散列值,组的大小不能超过1-2000。

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