C++0x编译时哈希

Question

使用GCC 4.4（通常是Android和IOS可用的最大版本），是否有一种方法可以对字符串进行编译时哈希处理。

我们有一个资源管理器，将字符串键映射到资源。虽然查找很快，但哈希和字符串创建较慢。类似于：

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

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

我想知道是否有一个技巧可以在编译时进行哈希处理。

- Halsafar

---

get函数的参数类型是什么？为了避免分配内存，请使用char const*。 - James McNellis

如果关键字在编译时已知，为什么不直接使用“枚举”（enum）呢？ - smocking

smoching是对的。为什么要在编译时进行哈希处理，让生活变得复杂呢？你可以使用一个简单的枚举，像这样：ResourcesManager::get<Texture>(Resources::SomeKey)。 - mfontanini

@DavidRodríguez-dribeas，我认为文本的地址不能保证在同一字符序列的不同实例化中相同。 - Mark Ransom

虽然对于纯资源来说，枚举（enum）是可以的。但某些资源引用键来自文件，应该在第一次使用时哈希化，而不是每次使用都进行哈希计算。更大的使用量来自于渲染例程访问着色器(uniforms)。通过字符串键查找uniforms的查找表。这将从编译时哈希中受益。由于uniform的位置在硬件之间不一致，因此无法使用枚举。话虽如此，代码库的业务逻辑类似于脚本编写。将查找保持为通用情况，而不是与一个不断增长的枚举耦合可能更加明智（至少现在是这样）。 - Halsafar

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。

- mfontanini

---

或许有助于澄清：constexpr函数具有非常严格的形式，不能使用循环。这就是为什么哈希很困难的原因。我也觉得禁止循环等等却允许递归非常奇怪。 - edA-qa mort-ora-y

这促使我去了解constexpr，我承认我之前还没有听说过它。除了性能分析（valgrind、gprof等），是否有一种方法可以验证constexpr确实在编译时计算？ - Halsafar

抱歉，这行不通。GCC 4.4不支持constexpr... http://wiki.apache.org/stdcxx/C%2B%2B0xCompilerSupport - Halsafar

@Halsafar 哦，抱歉，我没有注意到你正在使用gcc 4.4。嗯，这对那些试图在C++11中实现此目标的人可能很有用。 - mfontanini

供日后参考。XCode目前能够编译此代码。它似乎要么忽略了constexpr，要么就是可以接受它。Android仍在使用GCC 4.4，因此无法编译。但是谷歌提供了GCC 4.6源代码。现在正在尝试编译它们。 - Halsafar

Answer 2

为了进行编译时哈希，您的所有键都需要是编译时常量。

使用编译时常量进行索引的通常方法不是使用字符串，而是使用枚举类型。这样做的好处是根本不需要哈希，因为常量是连续的，并且可以直接索引数组。

enum KeyType
{
    someKey,
    someOtherKey
};

ResourcesManager::get<Texture>(someKey);

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

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

- Mark Ransom

Answer 3

您可以随时编译一个程序来哈希您的字符串并输出适当的源代码...

我个人不会实际哈希字符串，我只是枚举项目并输出具有枚举的头文件。非常简单易行，没有冲突等。

- Christian Stieber