散列函数：有没有办法进一步优化我的代码？

Question

以上是哈希函数。

我写了下面的代码。我不确定我是否可以用另一种聪明的方式来提高效率。我使用的理解是，我根本不需要执行mod，因为unsigned int通过溢出处理。

int myHash(string s) 
{ 
    unsigned int hash = 0; 
    long long int multiplier = 1; 
    for(int i = s.size()-1;i>-1;i--) 
    { 
     hash += (multiplier * s[i]); 
     multiplier *= 31; 
    } 
    return hash; 
} 

Answer 1

我会避免使用long long的乘数。至少如果你不知道你的处理器在32位乘法的同一时间内64位乘以100％。真正现代顶级的范围处理器可能就是这么做的，较旧的&较小的处理器几乎可以肯定需要较长时间才能完成64位mul操作，而不是32位处理器。

由31乘实际上是相当快的，即使对不擅长乘以处理器，因为x *= 31可以转换为x = x * 32 - x;或x = (x << 5) - x; - 事实上，它可能是值得一试的是[如果你还没有编译的代码汇编，看到编译器已经这样做了]。

除此之外，这将是我想到的处理器或编译器的优化具体。例如循环展开。或者使用内联汇编程序或内部函数来使用向量指令（取决于不同处理器体系结构和不同代的可用性）。像gcc或clang的最新版本的现代编译器可能会向量化这些代码，但会被赋予“正确的”选项。

与所有优化项目一样，使用具有代表性的工作负荷来衡量时间，记录您更改的内容。看看生成的代码，试图找出是否有更好的方法来做到这一点。并且不要忘记它是整体计划的表现很重要的事实。如果你花80％的时间在这个功能上，尽一切办法，优化它。如果你花费20％的时间，优化一点，如果你花费2％的时间，除非你可以做很多事情来改善它，它不会给你太多。我已经看到了人们编写代码的结果，以便在一些代码中节省几个时钟周期，这些代码需要在循环的两行中进行数百万次循环。并且使用一些小技巧来节省2个字节，大概需要半个兆字节。它只是造成混乱，并不值得做。

Answer 2

我想你可以做的说法没有对字符串复制的函数调用，使小号const string &s替代，或者用std::string_view，如果你碰巧使用C++ 17。否则，它看起来很快，你应该把剩下的东西留给编译器。尝试使用-O2或您的编译器等效来优化。

Answer 3

让我先说这可能是不值得做的 - 你的散列函数不太可能成为你程序中的瓶颈，所以使散列函数更加精细以提高它的效率可能会只是让它更难以理解和维护，而不会使您的计划更快地实现。所以不要这样做，除非你确定你的程序花费了很大一部分时间来计算字符串散列，并且确保你有一个很好的基准例程，你可以在这个变化的“之前”和“之后”运行来验证它确实可以显着加快速度，否则你可能只是在追逐彩虹。

也就是说，哈希长字符串更加迅速将处理串在一个时间一个字，而不是一次一个字符，像这样一个可能的方式：

unsigned int aSlightlyFasterHash(const string & s) 
{ 
    const unsigned int numWordsInString  = s.size()/sizeof(unsigned int); 
    const unsigned int numExtraBytesInString = s.size()%sizeof(unsigned int); 

    // Compute the bulk of the hash by reading the string a word at a time 
    unsigned int hash = 0; 
    const unsigned int * iptr = reinterpret_cast<const unsigned int *>(s.c_str()); 
    for (unsigned int i=0; i<numWordsInString; i++) 
    { 
     hash += *iptr; 
     iptr++; 
    } 

    // Then any "leftover" bytes at the end we will mix in to the hash the old way 
    const unsigned char * cptr = reinterpret_cast<const unsigned char *>(iptr); 
    unsigned int multiplier = 1; 
    for(unsigned int i=0; i<numExtraBytesInString; i++) 
    { 
     hash += (multiplier * *cptr); 
     cptr++; 
     multiplier *= 31; 
    } 
    return hash; 
} 

注意上面函数将返回不同于您提供的散列函数的散列值。

这由四个因素减少了循环迭代的次数;当然，这个功能的执行可能受到RAM带宽而不是CPU周期的限制，所以如果现代CPU的速度没有明显提高，那么就太惊讶了。如果RAM带宽确实是瓶颈，那么你可以做的事情不多，因为你必须读取字符串的内容才能计算字符串的散列码;除了预先计算哈希代码并将其存储在某个地方，但只有在您知道所有要提前使用的字符串的情况下才有效）。