多项式哈希函数是否有效？

Question

我想知道为什么没有讨论多项式哈希函数的效率（在时间和space方面）？我书中推荐的常量值是 33、37、39 和 41，但它们相当大。如果我的字符串是 15 a's (aaaaaaaa..) 然后计算 (41^15)(97)+(41^14)(97)+...... ( 97，因为 a) 的 ASCII 值是一项非常繁重的任务，如果我输入百万个条目，那么您可以想象。那么有人可以回答我的两个问题吗？

1. 是我弄错了这个函数的时间和space复杂性还是我对它的理解是正确的？

2. 如果我是对的，那我们为什么要使用它呢？我们能找到其他更好更有效的替代方案吗？

Answer 1

它是这样实现的：

int h=0;
foreach (character c in string)
{
    h = (h*41)+c;
}
return h;

如您所见，它并不显着 space 而且速度非常快。