c++ - STL __STL_hash_string

Question

struct str_hash{
    size_t operator()(const string& str) const
    {
            unsigned long __h = 0;
            for (size_t i = 0 ; i < str.size() ; i ++)
            __h = 5*__h + str[i];
            return size_t(__h);
    }
};

关于SGI STL中的字符串转换函数，为什么要用这个表达式？

__h = 5*__h + str[i];

Answer 1

这称为多项式哈希。对于某些 x(此处 x=5)，您考虑以下多项式:

str[0] * x^n + str[1] * x^(n-1) + ... + str[n] * x^0

你可以重写如下:

(((str[0] * x) + str[1]) * x + str[2]) * x + ... ) * x + str[n]

可以这样计算

h = 0
h = h * x + str[0] // h = str[0]
h = h * x + str[1] // h = (str[0] * x) + str[1]
h = h * x + str[2] // h = ((str[0] * x) + str[1]) * x + str[2]
...

可以看到这对应了你好奇的那一行:

 __h = 5*__h + str[i];

多项式散列在加密方面非常不安全，可能会在对抗性输入上造成严重的碰撞，但有时它并无大碍。它的主要优点是易于计算，并且通过 O(n) 预处理，您可以在 O(1) 时间内计算任何子字符串的散列。我个人觉得 x=5 的选择很差(我认为 x 至少大于字母表的大小)，但我不知道这个函数的细节申请。