编译字符类型的时间一致性散列

我想以类似于Symbol的方式实现ruby。编译字符类型的时间一致性散列

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

代码非常好，但是当我读somewhere时，哈希函数在同一程序的多次执行中可能不一致。此外，我想在编译时进行这种计算，这是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 ++（我认为增量运算符的未定义行为的问题），导致段错误。

在此先感谢

编辑

铿锵工作++（感谢KennyTM）

来源

2012-06-22 Geoffroy

我试过clang ++，但它不会崩溃。 – kennytm

谢谢:)我编辑帖子 – Geoffroy

有没有UB，它工作正常，只要字符串有'\0'终止。请注意，constexpr评估无法调用UB;在运行时导致UB的算术或指针操作需要在常量表达式的上下文中产生编译错误。

请注意，static_cast是不必要的; char操作数将被提升为size_t。

此外，乍一看散列函数看起来不太好，因为h * 31只是(h << 5) - h。你可以在整个二进制值中随机选择一个更大的数字。但另一方面，由于ASCII的低5位具有最大的熵，所以它们可能试图变得聪明，这消除了不同长度的短串之间发生碰撞的可能性。

来源

2012-06-22 08:53:00 Potatoswatter

感谢有关UB的精度。如果将constant_hash函数与另一个类型（如wchar_t）一起使用，或者甚至可以将其转换为size_t的任何其他类型，并且只要该数组以零终止，那么static_cast可能仍然有用。关于哈希函数，你认为我应该用（h << 5） - 1代替h * 31？ – Geoffroy

@Geoffroy：Potatoswatter意味着你可以选择一个更好的散列函数，而不是用'（h << 5）-h'来代替'h * 31'。由于向后兼容，Java需要使用'h * 31'，所以不需要。 – kennytm

好的，谢谢你的精确度，我不明白他的意思。你知道任何满足相同条件的散列实现吗？ – Geoffroy

注意：n3333是C++ 17的建议。尽管我不相信C++ 11需要在多次运行时产生相同的结果，但实际上我相信所有当前的实现都是如此。

来源

2012-06-22 14:27:33 Nevin

所有的实现可能暂时做它，但C++ 1y可能会指定散列函数从一个执行到另一个执行，只是为了防止危险的习惯。或者只是指定它不能改变。我们会看到:) – Geoffroy

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

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

这就是说，如果你正在使用std::hash，你不能保证该值将永远是执行之间相同的（并且在未来，如果n3333被采纳，这依赖于任何代码将打破），所以如果需要稳定散列，最好定义自己的稳定散列函数。

来源

2012-06-22 16:13:43 fluffy

感谢您的精确:) – Geoffroy

编译字符类型的时间一致性散列

回答

相关问题