c++ - 编译时散列 C++0x

Question

使用 GCC 4.4（通常是 Android 和 IOS 可用的最大值）有一种方法可以对字符串进行编译时散列。

我们有一个将字符串键映射到资源的资源管理器。虽然查找速度很快，但散列和字符串创建速度很慢。就像是：

 ResourcesManager::get<Texture>("someKey");

花费大量时间分配字符串“someKey”，然后对其进行哈希处理。

我想知道是否有一个技巧可以在编译时使用它来散列它。

Answer 1

您必须实现正确的散列算法，但这可以使用 C++11 的 constexpr 函数来工作：

#include <iostream>

// Dummy hashing algorithm. Adds the value of every char in the cstring.
constexpr unsigned compile_time_hash(const char* str) {
    // Modify as you wish
    return (*str == 0) ? 0 : (*str + compile_time_hash(str + 1));
}   

int main() {
    unsigned some_hash = compile_time_hash("hallou");
    std::cout << some_hash << std::endl;
}

然后你可能有一个重载，ResourcesManager::get它的结果是compile_time_hash（在这种情况下是无符号的）。

这显然取决于您应用的散列算法。使用 constexpr 实现类似 SHA* 的东西会非常痛苦。

请注意，您需要 GCC >= 4.6 或 clang >= 3.1 才能使用 constexpr。

Answer 2

为了进行编译时散列，所有键都需要是编译时常量。

使用编译时常量进行索引的常用方法不是使用字符串，而是使用枚举类型。这具有根本不需要散列的优点，因为常量是连续的并且可以直接索引数组。

enum KeyType
{
    someKey,
    someOtherKey
};

ResourcesManager::get<Texture>(someKey);

如果需要将键作为字符串获取，只需保留一个可以由枚举常量索引的字符串表。

static char * keyNames = 
{
    "someKey",
    "someOtherKey"
};

Answer 3

你总是可以编译一个程序来散列你的字符串并输出合适的源代码......

我自己，我实际上并没有对字符串进行散列，我只是枚举项目并输出带有枚举的头文件。很好很容易，没有冲突等。