4

我想以Symbol与 ruby​​ 相同的方式实现。

为此，我创建了一个用户定义的文字，它返回对应std::hash的a std::basic_string<T>。

代码很棒，但是当我在某处读到时，哈希函数在同一程序的多次执行中可能不一致。此外，我想在编译时进行此计算，这是 1) 不支持std::hash和 2) 如果std::hash返回值更改会破坏代码。

所以我写了下面的实现，基于java.lang.String.hashCode实现。

typedef size_t symbol;

template<typename CharT>
constexpr size_t constant_hash(const CharT* p, size_t h = 0) noexcept
{
    return (*p == 0) ? h : constant_hash(p + 1, h * 31 + static_cast<size_t>(*p));
}

constexpr symbol operator "" _sym (const char* p, size_t n) noexcept
{
    return constant_hash(p);
}

我的问题是：这个实现有什么问题吗？

我只能在 GCC 4.7.1 上对其进行测试，我想知道它是否符合标准并且也应该在其他编译器上工作。

我问这个是因为以前的实现是在 GCC 上工作的，但是如果二进制文件是用 clang++ 编译的，则会导致段错误（我认为增量运算符的未定义行为问题）。

提前致谢

编辑

使用 clang++（感谢 KennyTM）

4

3 回答 3

2

注意：n3333 是针对 C++17 的提议。虽然我不认为 C++11 要求哈希在多次运行时产生相同的结果，但实际上，我相信所有当前的实现都可以。

于 2012-06-22T14:27:33.527 回答
2

没有 UB，只要字符串有'\0'终止符，它就可以正常工作。请注意，constexpr评估不能调用 UB；在运行时导致 UB 的算术或指针操作需要在constant-expression的上下文中产生编译错误。

请注意，这static_cast是不必要的；操作数将char提升为size_t.

此外，乍一看，哈希函数看起来不太好，因为h * 31它只是( h << 5 ) - h. 您可能会选择一个更大的数字，其中 1 随机分布在整个二进制值中。但另一方面，他们可能试图变得聪明，因为 ASCII 的低 5 位具有最大的熵，这消除了不同长度的短字符串之间发生冲突的可能性。

于 2012-06-22T08:53:00.837 回答
1

在当前活跃的 C++ 标准中，散列函数的定义通常以这种方式编写，以便为特定领域的实现提供更多可能性，而不是要求以特定方式执行散列。例如，它允许使用池化字符串并将池实例的内存位置用作哈希值（顺便说一句，这就是 ruby​​ 处理其字符串及其哈希的方式，这导致了一些有趣的问题）。如果您正在计算数据的散列，而不是参考，那么该值将是稳定的 - 除非您发现了某种形式的数学，而常量表达式不是。

基本上，在这种情况下，“可能不”是允许事物以特定方式运行，而不是说明可能发生的事情。

也就是说，如果您使用std::hash，则无法保证执行之间的值始终相同（并且将来，如果采用 n3333 ，则任何依赖于它的代码都会中断），因此最好定义自己的如果您需要稳定的哈希，请使用稳定的哈希函数。

于 2012-06-22T16:13:43.383 回答