代码之家  ›  专栏  ›  技术社区  ›  Gayan

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

  •  4
  • Gayan  · 技术社区  · 15 年前

    我想将字符数组散列为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);
    }
    

    但是,在某些情况下,这会产生重复的值。 有没有什么好的替代方法不会为不同的字符串值复制相同的哈希值。

    4 回复  |  直到 15 年前
        1
  •  13
  •   ASk    15 年前

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

    理论上,32位散列有足够的范围来散列所有~6个字符串(仅a-Z、a-Z、0-9),而不会造成冲突。实际上,哈希并不是输入的完美排列。给定32位散列,由于 birthday paradox

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

    尽管如此, here

        2
  •  2
  •   sharptooth    15 年前

    每个散列都会有冲突。时期那叫一个 Birthday Problem .

    您可能希望检查加密函数是否具有类似MD5的功能(相对较快,您不在乎它是否不安全),但它也会发生冲突。

        3
  •  2
  •   Talljoe    15 年前

    散列为不同的输入生成相同的值——这就是它们所做的。您所能做的就是创建一个具有足够分布或位深度(或两者)的哈希函数,以最小化这些冲突。因为你有这个额外的精度限制(0-5?),那么你将更频繁地碰撞。

        4
  •  1
  •   Adam Matan    15 年前

    MD5 SHA . 有许多开放的实现,其结果不太可能产生重复的结果。