如何使用c ++将字符串散列为int？

Question

我必须编写自己的哈希函数.如果我想制作简单的哈希函数,将字符串中的每个字母映射到一个数值(即a = 1,b = 2,c = 3,...),有没有办法可以执行此哈希一个字符串,而不必先将其转换为一个c字符串来查看每个字符？是否有更有效的散列字符串方法？

Answer 1

根据个人经验,我知道这有效并产生良好的分布.(抄袭http://www.cse.yorku.ca/~oz/hash.html):

djb2

这个算法(k = 33)是多年前dan bernstein在comp.lang.c中首次报道的.该算法的另一个版本(现在bernstein青睐)使用xor:hash(i)= hash(i-1)*33 ^ str [i]; 33号的神奇之处(为什么它比许多其他常数(优质或非常)效果更好)从未得到充分的解释.

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}

Answer 2

重新提出第一个问题,例如:

int hash = 0;
int offset = 'a' - 1;
for(string::const_iterator it=s.begin(); it!=s.end(); ++it) {
  hash = hash << 1 | (*it - offset);
}

关于第二种,有很多更好的方法来散列字符串.例如,请参阅此处了解一些C示例(可以根据上面的代码段轻松转换为C++).

Answer 3

您可以使用[]运算符检查std :: string中的每个char .但是,您可以查看Boost :: Functional/Hash以获得更好的散列方案的指导.此处还有c中的散列函数列表.

Answer 4

这是我在Stroustrup的书中找到的C(++)哈希函数:

int hash(const char *str)
{
    int h = 0;
    while (*str)
       h = h << 1 ^ *str++;
    return h;
}

如果你将它用于哈希表(Stroustrup会这样做),那么你可以改为以模数的形式返回哈希模数.所以与其

    return (h > 0 ? h : -h) % N_BUCKETS;

为最后一行.