具有精度的字符串转整数哈希函数

Question

具有精度的字符串转整数哈希函数

4

我希望将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"。

然而，在某些情况下，这会产生重复值。是否有任何好的替代方案，可以避免为不同的字符串值生成相同的哈希值。

- Gayan

尝试使用 CRC 32：http://en.wikipedia.org/wiki/Crc32 - Akira Yamamoto

4个回答

2

每个哈希都会发生冲突。这被称为生日问题。

您可能希望检查像MD5这样的加密哈希函数（相对快速且您不关心它是否安全），但它也会发生冲突。

- sharptooth

完美哈希在定义上不会。 - MSalters

2

哈希函数会为不同的输入生成相同的值--这就是它们的作用。你能做的只是创建一个具有足够分布或位深度（或两者兼备）的哈希函数，以尽量减少这些冲突。由于你还有这个精度的额外限制（0-5 ?），那么你会更经常地遇到冲突。

- Talljoe

1

MD5或SHA。有许多开放的实现，结果很不可能产生重复的结果。

- Adam Matan

是的。但我的要求还包括结果必须是整数。MD5哈希包含整数和字符。我认为SHA算法也是一样的。 - Gayan

真的，但是转换很简单-从128位到32位整数。您将得到一个两行代码（哈希，int转换），可以生成事实上没有冲突的哈希。 - Adam Matan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ASk · Accepted Answer

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

理论上，32位哈希具有足够的范围来哈希所有长度为~6个字符的字符串（仅限A-Z,a-z,0-9），而不会发生冲突。实际上，哈希并不是输入的完美排列。给定一个32位哈希，你可以期望在哈希了随机输入的 ~16 位后出现哈希冲突，这是由于生日悖论造成的。

对于一组静态的数据值，始终可以构造一个专门为它们设计的哈希函数，它将永远不会与自身冲突（当然，其输出的大小至少为 log（|data set|））。但是，这需要你事先知道所有可能的数据值。这被称为完美哈希。

话虽如此，在这里有几种替代方案可供选择（它们都是为了最小化哈希冲突而设计的）。