c - 将 int16_t 哈希为 uint64_t

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 4 年前。

Improve this question

我正在尝试为 int16_t 创建一个哈希函数。函数原型(prototype)如下所示:

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 位无符号整数就可以了？如果整数为负数，当我将其转换为无符号类型时，我会丢失信息吗？这会产生未定义的行为吗？

附注代码是 C 语言，我从 here 中获取了哈希函数。 .

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

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

Answer 1

Is there a hash function for signed types?

当然。适用于无符号类型的良好哈希函数也可以适用于有符号类型。如果哈希函数好，那么它就有好 uniformity ，因此将特定位称为“符号位”或“只是另一位”并不重要。出于本答案的目的，我将认为您在链接线程中找到的算法是“好的”。

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

您不能依赖位移运算符来提升将 uint16_t 移位到 uint64_t 的结果，因此您必须使用 uint64_t code> 如您发布的代码所示。

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。

<小时/>

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

return (uint64_t) x;

该函数没有色散，但输入和输出范围具有(简单的)最佳均匀性。这是否可以接受取决于哈希表的实现。如果它天真地仅使用哈希值的某些位来选择一个容器来放置该值，并且它自己不进行任何混合，那么您需要将输出的一致性集中在这些位上，无论在哪里/无论它们是什么。