字符串开关的哈希函数

Question

我正在尝试在C++中使用哈希来切换字符串，并使其工作。这段代码已经变成了我和它之间的个人问题，所以即使最终只有8个字符串要放在switch语句中，我也不想放弃并使用enum。

结合我在其他话题上看到的内容，我编写了这个非常简单且不太可靠的函数，但对于我想做的事情来说已经足够了，因为这并不是职业性质的。我的函数：

constexpr long hashstr (const string &str, int h=0)
{
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];
}

我现在只是写了一个非常简单的主函数，然后调用它，但编译不过，提示我case是错误的（不是常量）。我不明白这个问题，因为我认为作为参数传入的字符串是一个常量，并且该函数返回一个常量表达式。

我的主函数：

int main (void) {

    string teststr;
    cout << "test string :::>  ";
    cin >> teststr;
    int tt = hashstr(teststr);
    cout << "res -->  " << tt << endl;

    switch ( hashstr(teststr) )
    {
    case hashstr("rosathefloridaturtle") :
        cout << "ROSA OK" << endl;
        break;

    default:
        cout << "ERROR" << endl;
        break;
    }

    return EXIT_SUCCESS;
}

希望你们中的一些人能告诉我我哪里做错了...

- sinatrablue

---

请不要标记垃圾邮件。使用 [tag:c++] 和其中之一的 [tag:c++11]、[tag:c++14] 或 [tag:c++17]。 - klutt

请勿描述错误消息。请发布精确的错误消息。 - klutt

你的 hashstr 定义也不应该编译通过（至少在 gcc 中不会），因为字符串索引不是 constexpr，所以第二个错误是无关紧要的。 - vgru

你可能会发现Coding up a Hash Table和Hash tables - eternally confuzzled很有用。考虑使用openSSL库中提供的lh_strhash。它是高效的，可以最小化字符串哈希的冲突（真的很好）。 - David C. Rankin

@TonyK 我非常高兴，Rosa肯定也很满意，她是个讨厌的家伙。 - sinatrablue

Answer 1

除非您正在使用c++20，否则std::string不是constexpr，因此无法在hashstr中使用。

返回的值大于long的表示范围，由于有符号算术溢出是未定义行为，因此您的代码不能在constexpr中使用。

修复这两个问题可以得到可用的代码:

constexpr unsigned long hashstr (const std::string_view &str, int h=0)
{
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)(str[h]);
}

请注意，如果您查看编译器输出，它可能会告诉您为什么您的表达式不是constexpr，例如，clang会打印以下信息：

error: case value is not a constant expression
    case hashstr("rosathefloridaturtle") :
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:22:18: note: non-literal type 'const std::string' (aka 'const basic_string<char>') cannot be used in a constant expression
    case hashstr("rosathefloridaturtle") :

更改为std::string_view会打印：

error: case value is not a constant expression
    case hashstr("rosathefloridaturtle") :
         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>:9:47: note: value 97009635813568987014 is outside the range of representable values of type 'long'
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];
                                              ^
<source>:9:29: note: in call to 'hashstr("rosathefloridaturtle", 8)'
    return !str[h] ? 55 : ( hashstr(str, h+1) *33) + (unsigned char)str[h];

- Alan Birtles

---

为什么要使用 const std::string_view&？ - Passer By

@PasserBy 没有什么特别的危害，只是从原始帖子的代码中复制而来。即使 string_view 应该很便宜，但递归传递引用仍然比复制字符串视图更便宜。 - Alan Birtles

假设递归没有被优化掉，鉴于它是一个微不足道的类型，按值传递将在寄存器中完成，而引用必须在堆栈上传递。我猜两者都将是noops，并且按值传递可以节省最终的间接寻址。但这些都不重要，string_view& 看起来就像 int*&，非常奇怪。 - Passer By

使用该引用会导致clang在优化禁用的情况下生成更少的代码：https://godbolt.org/z/5Ed93a - Alan Birtles

这是 quick-bench。我刚刚意识到为什么它如此奇怪：我们传递了一个多余的 h。而且，使用加法作为哈希值是一个极其糟糕的想法。没有 h，按值传递的 quick-bench 看起来好多了。 - Passer By

是的，您修改后的代码正在创建新对象，这使得通过引用传递变得毫无意义。 - Alan Birtles

Answer 2

正如 @Alan Birtles 所说，根据您当前使用的编译器标准，std::string 不是一个 constexpr，因此您不能像这样使用。

但好消息是，您不需要使用 std::string_view！只需使用 std::string::c_str() 并使用 char 指针获取哈希值即可。

另外，根据需求，我认为您可能想要使用一种称为 natural overflow 的技术，它在哈希中广泛使用（实际上它是一个模函数，但删除了模运算符，该运算符也表示模 MAX_VALUE），但它使用的类型是 unsigned 整数，正如 Alan 提到的那样，有符号溢出可能会触发 ub。因此，请改用无符号类型。

以下是我实现此用法的代码。

#include <iostream>
#include <string>

using namespace std;

using ull = uint64_t;

constexpr ull hashstr(const char* s, size_t index = 0) {
    return s + index == nullptr || s[index] == '\0' ? 55 : hashstr(s, index + 1) * 33 + (unsigned char)(s[index]);
}

constexpr const char* a = "rosathefloridaturtle";

int main() {
    string s;
    cout << "test string :::>  ";
    cin >> s;
    ull tt = hashstr(s.c_str());
    cout << "res -->  " << tt << endl;
    switch (tt) {
        case hashstr(a):
            cout << "ROSA OK" << endl;
            break;
        default:
            cout << "ERROR" << endl;
            break;
    }
    return 0;
}

- SHP