c++ - 字符串到整数的精确哈希函数

我想将一个 char 数组散列为一个 int 或 long。结果值必须遵守给定的精度值。我一直在使用的功能如下:

int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}

待哈希的字符串类似于“SAEUI1210.00000010_1”。

但是，这在某些情况下会产生重复值。是否有任何好的替代方案不会为不同的字符串值复制相同的哈希值。

最佳答案

散列的定义是，由于散列值范围小于散列数据的空间，它会为某些值产生重复值。

理论上，32 位散列的范围足以散列所有 ~6 个字符串(仅限 A-Z、a-z、0-9)，而不会导致冲突。实际上，哈希并不是输入的完美排列。给定一个 32 位哈希，由于 birthday paradox，您可以预期在对 ~16 位随机输入进行哈希处理后会发生哈希冲突。 .

给定一组静态数据值，总是可以构造一个专门为它们设计的哈希函数，它永远不会与自身发生冲突(当然，其输出的大小至少为 log(|data set |)。但是，它要求您提前知道所有可能的数据值。这称为 perfect hashing。

也就是说，here有一些可以帮助您入门的备选方案(它们旨在最大程度地减少冲突)

关于c++ - 字符串到整数的精确哈希函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1010875/