0

我正在尝试为int16_t. 函数原型如下所示：

uint64_t hash_int16_t(const void *key);

到目前为止，我已经得到了这个，但我不知道这是否是正确的方法：

uint64_t hash_int16_t(const void *key)
{
    // key is expected to be an int16_t
    const int16_t *e = (const int16_t*)key;

    uint64_t x = (uint64_t)*e;

    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);

    return x;
}

有符号类型有哈希函数吗？我应该使用 16 位无符号整数或 64 位无符号整数来混合这些位吗？如果整数为负数，当我将其转换为无符号类型时，我会丢失信息吗？这会产生未定义的行为吗？

PS 代码在 C 中，我从这里获取了哈希函数。

编辑 1：该参数是const void *key因为允许用户将键存储为其他值，如结构或字符串。上述功能将添加对int16_t键的支持。

编辑2：我想要完成的是一个通用哈希表。初始化哈希表时，用户必须提供一个哈希函数，上面的示例与哈希表捆绑在一起。

4

1 回答 1

0

有符号类型有哈希函数吗？

当然。适用于无符号类型的良好哈希函数也适用于有符号类型。如果散列函数很好，那么它就具有很好的一致性，因此无论您将特定位称为“符号位”还是“只是另一个位”都没有关系。出于此答案的目的，我认为您在链接线程中找到的算法是“好的”。

我应该使用 16 位无符号整数或 64 位无符号整数来混合这些位吗？

您不能依靠位移运算符来提升将 a 转换uint16_t为 a的结果uint64_t，因此您必须uint64_t按照您发布的代码中的方式使用。

如果整数为负数，当我将其转换为无符号类型时，我会丢失信息吗？

不，因为 a 的每个可能值int16_t在转换为 a 时都映射到不同的值uint64_t：范围 [0, 32767] 映射到 [0, 32767] 并且范围 [-32768, -1] 映射到 [18446744073709518848, 18446744073709551615] （解释见下文）。

这会产生未定义的行为吗？

否。C 标准 (C11) 为有符号到无符号整数转换指定以下内容（第 6.3.1.3 节）：

[...] 如果新类型是无符号的，则通过重复在新类型中可以表示的最大值加或减 1 来转换该值，直到该值在新类型的范围内。

因此，-32768 转换为 -32768 + 2 64 = 18446744073709518848，-1 转换为 -1 + 2 64 = 18446744073709551615。

至于算法本身......如果哈希值仅用于创建哈希表，那么哈希函数不需要具有任何加密属性，如分散。因此，这个简单的算法可能适用于int16_t x：

return (uint64_t) x;

此函数没有分散，但（微不足道）输入和输出范围的最佳均匀性。这是否可以接受将取决于哈希表的实现。如果它天真地只使用哈希值的某些位来选择一个 bin 来放置值，并且它自己不做任何混合，那么您需要将输出的均匀性集中在这些位上，无论在哪里/不管他们是谁。

于 2018-12-12T17:39:47.717 回答