我有一个结构体,它由五个std::uint8_t组成。我的软件不支持32位版本,只支持64位版本。我想用我的结构体作为无序Map中的键。我可以只添加三个额外的字节到结构体,以填补完整的64位,并将结构体转换为size_t,以获得安全的哈希?像这样:
struct MyStruct
{
std::uint8_t v1 = 0;
std::uint8_t v2 = 0;
std::uint8_t v3 = 0;
std::uint8_t v4 = 0;
std::uint8_t v5 = 0;
std::uint8_t pack1 = 255;
std::uint8_t pack2 = 255;
std::uint8_t pack3 = 255;
};
namespace std
{
template <>
struct hash<MyStruct>
{
size_t operator()(const MyStruct &s) const
{
static_assert(sizeof(size_t) == 8);
static_assert(sizeof(MyStruct) == 8);
const size_t *memptr = reinterpret_cast<const size_t*>(&s);
return *memptr;
}
};
}
3条答案
按热度按时间oalqel3c1#
所提出的解决方案倾向于未定义的行为,至少是因为
memptr
可能不满足size_t
的对齐要求。更好的替代方法是使用
memcpy
:不管结构体和
size_t
之间的大小差异如何,这都应该起作用,但当然只会区分前sizeof(size_t)
字节上的两个结构体。这对你的结构体来说应该不是问题,但是通常,你必须意识到一个结构体可能包含padding bytes,这些padding bytes具有不受控制的值,这些值可能会扰乱哈希结果。
fdbelqdn2#
您需要该类型作为标准无序容器的键,并且它的大小小于
std::size_t
。因此,位模式可以用作完美散列函数。你不需要奇怪的技术:如果编译器不能优化它,更复杂的版本将是:
总结一下:
这将修改结果的情况下
std::hash
内置积分是任何以外的单位。如果您更喜欢完美散列,则可以跳过作为整数的重散列,以避免可能导致冲突概率的截断。jobtbby33#
我可以只添加三个额外的字节到结构体,以填补完整的64位,并将结构体转换为size_t,以获得安全的哈希?
否-正如其他人所提到的,由于MyStruct可能具有与
size_t
不同的对齐方式,并且由于别名(您只能安全地通过char*
,unsigned char*
或std::byte*
reinterpret_cast
size_t
),您将具有未定义的行为。从C20开始,std::bitcast
是推荐的方法:std::bitcast<size_t>(some_MyStruct_object)
。虽然上面的话已经被Red.Wave和Nielsen说了,但Red.Wave提到:
如果内置积分的std::hash是除identity以外的任何值,则这将修改结果。
实际上,
std::hash<size_t>
--据我所知--是clang、GCC和MSVC中的一个身份哈希函数。当然,在clang和GCC的当前版本和所有模糊的reent版本中(我刚刚重新检查了godbolt)。幸运的是,他们使用素数来计算桶数,所以这并不重要。但是MSVC在历史上(我想仍然是这样,但是godbolt不会在MSVC下执行代码)使用2的幂来计算桶数,所以这很重要。在MSVC++和任何其他使用2的幂次桶计数的实现中,简单的位播方法将产生可怕的哈希表冲突。当散列函数返回一个数字时,它通过用桶数-1进行掩码而被折叠到bucket_count中,这实际上仅使用标识桶所需的最低有效位中的许多位(对于64个桶-> 6位,对于128个桶-> 7位等)。
为了使这一点更清楚,假设您的
MyStruct
对象具有值{ab,cd,ef,gh,ij,pad 1,pad 2,pad 3} -其中两个字母的组合表示您的uint8_t
s的2位十六进制值表示,并且您的哈希表bucket_count当前为256。你散列你的对象,最后得到- it your little endianness - FFFF'FFij'ghef'cdab。然后屏蔽掉低阶8位以获得0..255桶索引。只有来自MyStruct
对象的字节- ab -会影响哈希/掩码到的存储桶。如果你的数据是{1,2,3,4,5},{1,202,18,48,2},{1,7,27,87,85},{1,48,26,58,16} ->所有这些条目都将在存储桶1处发生冲突。然后,哈希表就像一个链表一样运行。如果在size_t
中,使用endianness将填充字节移动到不太重要的位位置,则它们不会对随机化/分散您的桶使用做出丝毫贡献。虽然首先使用
bitcast
从MyStruct
生成size_t值是合理的,但您可能希望随后对其执行一些实际的、有意义的散列。如前所述,您通常不能简单地在其上调用std::hash<size_t>()
,因为这通常是一个身份散列。因此,找到一个SO问题或引用,其中包含size_t的适当散列,或者使用类似Intel CRC指令_mm_crc32_u64
的东西。(因为这些事情很棘手,实现选择有时令人惊讶,当你有理由关心性能时,通常最好用你的数据和哈希函数来测量冲突链长度,以确保你没有意外的冲突率。