使用Precision的字符串到整数哈希函数

Question

我想将一个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".

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

Answer 1

散列的定义是它为某些值生成重复值,因为散列值范围小于散列数据的空间.

理论上,32位散列具有足够的范围来散列所有~6个字符串(仅AZ,az,0-9),而不会导致冲突.在实践中,散列并不是输入的完美排列.给定32位散列,由于生日悖论,在散列~16位随机输入后,您可能会遇到哈希冲突.

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

话虽如此,这里有一些替代方案可以让你开始(它们旨在最大限度地减少碰撞)