gpt4 book ai didi

c++ - 三个有符号整数的哈希函数

转载 作者:行者123 更新时间:2023-11-28 00:23:21 25 4
gpt4 key购买 nike

我正在尝试使用带有三个带符号整数的 unordered_map 作为键(这是因为我想使用 tbb 的 concurrent_unordered_map)。

我把这个小(3x16 位 => 64 位)函数放在一起:

// to hash

int64_t result = int16_t(x);

result = int64_t(result << 16) + int16_t(y);
result = int64_t(result << 16) + int16_t(z);

// from hash

int16_t x_ = int16_t(result >> 32);
int16_t y_ = int16_t(result >> 16);
int16_t z_ = int16_t(result & 0xFFFF);

这不起作用,我在这里犯了什么错误?

我的数字分布使得负数或正数更接近于零(通常小于 +/- 2^8),但我想将其扩展到最大 2^32 的范围,而不是我这里的 2^16 示例。理想情况下,我正在寻找典型范围内尽可能少的碰撞,最好是一个简单的算法。有什么建议吗?

最佳答案

您的问题是您正在执行位操作并添加有符号数。如果数字是负数,加法运算将转化为减法。发生这种情况后,将很难梳理出正确的原始值。

考虑:

int16_t x = -1, y = 2, z = -3;
int64_t result = x; // result: FFFFFFFFFFFFFFFF
result = (result << 16) + y; // result: FFFFFFFFFFFF0000 + 0002
result = (result << 16) + z; // result: FFFFFFFF00020000 - 0003
return result; // result: FFFFFFFF0001FFFD

因此,虽然 -1-3 已被保留,减法的结果已将 2 减少到 1.

相反,您应该限制对无符号值的操作。对于无符号值,+| 在您的代码中将是等效的,因为您要添加到被 0 填充的数字部分。

int64_t hash () {
uint64_t result = uint16_t(x_);
result = (result << 16) + uint16_t(y_);
result = (result << 16) + uint16_t(z_);
return result;
}

关于c++ - 三个有符号整数的哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26348301/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com