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至少大于字母表的大小），但我不知道此功能应用程序的详细信息。