STL __stl_hash_string
STL __stl_hash_string
提问于 2018-12-02 07:34:52
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中的字符串转换函数，为什么要使用这个表达式？
__h = 5*__h + str[i];回答 1
Stack Overflow用户
回答已采纳
发布于 2018-12-02 07:47:58
这被称为多项式哈希。对于某些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至少比字母表大)，但我不知道这个函数应用程序的细节。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53578314
复制相关文章
相似问题
腾讯云开发者
