哈希 int16_t 到 uint64_t

Question

我正在尝试为 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 位无符号整数来混合这些位吗？如果整数为负，将其转换为无符号类型时是否会丢失信息？这会产生未定义的行为吗？

P.S。代码在 C 中，我从 here.

中获取了哈希函数

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

编辑 2：我要完成的是通用哈希 table。用户在初始化散列 table 时必须提供散列函数，上面的示例与散列 table.

捆绑在一起

Answer 1

Is there a hash function for signed types?

当然可以。适用于无符号类型的良好哈希函数也适用于有符号类型。如果散列函数很好，那么它就有很好的 uniformity，因此将特定位称为 "sign bit" 或 "just another bit." 并不重要。为了这个答案的目的，我假设您在链接线程中找到的算法是 "good."

Should I mix the bits using 16 bit unsigned integers or 64 bit unsigned integers will do fine?

您不能依靠位移运算符来提升将 uint16_t 移动到 uint64_t 的结果，因此您必须像在代码中一样使用 uint64_t已发布。

Will I be loosing information when I cast it to an unsigned type if the integer is negative?

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

Will this generate undefined behavior?

没有。 C 标准 (C11) 指定以下符号到无符号整数转换 (§6.3.1.3)：

[...] if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

因此，-32768转换为-32768 + 2⁶⁴ = 18446744073709518848，-1转换为-1 + 2⁶⁴ = 18446744073709551615.

至于算法本身...如果哈希值仅用于创建哈希 [=49=]，则哈希函数没有必要具有任何加密色散等特性。因此，这个简单的算法可能适用于 int16_t x:

return (uint64_t) x;

此函数没有色散，但（平凡地）输入和输出范围的最佳均匀性。这是否是 acceptable 将取决于散列 table 实现。如果它天真地只使用散列值的某些位到 select 一个 bin 来放置值，并且它自己不进行任何混合，那么您需要将输出的一致性集中在那些位，wherever/whichever 他们是。

哈希 int16_t 到 uint64_t

Hashing int16_t to uint64_t

c

hash

hash-function

signed-integer