用于打开字符串的哈希函数

Question

我正在尝试借助散列在 C++ 中对字符串进行切换。它成为我和这段代码之间的私人关系，所以我不想放弃并使用枚举，即使我最终只有 8 个字符串可以放入 switch cases。

结合我在其他题目上看到的，我写了这个很简单的功能，不是很靠谱，但是对于我想做的事情已经足够了，不专业。

我的函数：

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

然后我在这个非常简单的主函数中调用它（现在），但它不会编译，告诉我大小写错误（不是常量）。我不明白这个问题，因为我的arg中的字符串是一个常量，加上函数returns一个常量表达式。

我的主要 :

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;
}

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

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，例如铿锵打印：

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];

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] == '[=10=]' ? 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;
}

用于打开字符串的哈希函数

Hash function to switch on a string

c++

hash