长字符串键的快速哈希函数

Question

我正在使用可扩展哈希，我想将字符串作为键。问题是我正在使用的当前哈希函数在整个 string/key 上迭代，我认为这对程序的性能非常不利，因为哈希函数被多次调用，尤其是当我拆分桶时。

当前哈希函数

int hash(const string& key)
{
    int seed = 131;
    unsigned long hash = 0;
    for(unsigned i = 0; i < key.length(); i++)
    {
        hash = (hash * seed) + key[i];
    }
    return hash;
}

密钥最长可达 40 个字符。

string/key

的例子

string key = "from-to condition"

我在互联网上搜索了更好的，但没有找到符合我的情况的东西。有什么建议吗？

Answer 1

您应该更喜欢使用 std::hash，除非测量表明您可以做得更好。要限制它使用的字符数，请使用类似：

    const auto limit = min(key.length(), 16);
    for(unsigned i = 0; i < limit; i++)

您需要通过试验找到 16 的最佳值。

我实际上预计性能会变得更差（因为你会有更多的碰撞）。如果您的字符串有几 k，那么限制在前 64 个字节可能是值得的。

根据您的字符串，可能值得从头开始。例如，散列文件名你最好使用从末尾开始的 20 到 5 之间的字符（忽略通常不变的路径名前缀和文件扩展名）。但是还是得量一下。

Answer 2

你可以直接使用std::hashlink而不是自己实现功能

#include <iostream>
#include <functional>
#include <string>

size_t hash(const std::string& key)
{
    std::hash<std::string> hasher;
    return hasher(key);
}

int main() {
    std::cout << hash("abc") << std::endl;
    return 0;
}

在此处查看此代码：https://ideone.com/4U89aU

Answer 3

I am using an extendible hash and I want to have strings as keys.

如前所述，使用 std::hash 直到有充分的理由不使用。

The problem is that the current hash function that I am using iterates over the whole string/key and I think that this is pretty bad...

这是一个可以理解的想法，但实际上不太可能成为真正的问题。

(anticipating) why?

快速浏览堆栈溢出会发现许多经验丰富的开发人员都在谈论缓存和缓存行。

（教我奶奶吸鸡蛋见谅）

现代 CPU 在处理指令和执行（非常复杂的）算术方面非常快。在几乎所有情况下，限制其性能的是必须通过总线与内存通信，相比之下，速度慢得可怕。

因此芯片设计者构建了内存缓存 - 位于 CPU 中的极快内存（因此不必通过慢速总线进行通信）。不幸的是，这个缓存内存只有这么多 space 可用 [加上热限制 - 另一天的话题] 所以 CPU 必须像 OS 做磁盘缓存一样对待它，在需要时刷新内存并读取内存。

如前所述，通过总线进行通信很慢——（简单地说）它需要主板上的所有电子元件停止并相互同步。这浪费了大量时间[讨论电子信号在主板上的传播受到大约一半光速的限制——这很有趣，但只有这么多 space在这里，我只有这么多时间]。因此，不是一次传输一个字节、一个字或一个长字，而是以块的形式访问内存——称为缓存行。

事实证明，这是芯片设计人员的一个很好的决定，因为他们明白大多数内存是按顺序访问的——因为大多数程序花费大部分时间线性访问内存（例如计算哈希、比较字符串或对象时、转换序列、复制和初始化序列等）。

这一切的结果是什么？

好吧，奇怪的是，如果你的字符串还没有在缓存中，那么读取它的一个字节几乎和读取第一个字节中的 all 个字节一样昂贵（比如说）它的 128 个字节。

另外，因为缓存电路假定内存访问是线性的，所以它会在获取您的第一个缓存行后立即开始获取下一个 缓存行。它会在您的 CPU 执行其哈希计算时执行此操作。

我希望你能看到，在这种情况下，即使你的字符串有数千个字节长，并且你选择只散列（比方说）每 128 个字节，你要做的就是计算一个非常劣质散列仍然导致内存缓存在获取大块未使用内存时停止处理器。 它会花费同样长的时间 - 更糟糕的结果！

Having said that, what are good reasons not to use the standard implementation?

仅当：

用户抱怨你的软件速度太慢用不上，
程序是可验证的CPU绑定（使用100%的CPU时间），并且
程序没有通过旋转浪费任何周期，并且
仔细分析发现程序最大的瓶颈是散列函数，
另一位经验丰富的开发人员的独立分析证实，没有办法改进算法（例如，减少调用散列的频率）。

简而言之，几乎没有。

长字符串键的快速哈希函数

Fast hash function for long string key

c++

hash-function