c++ 高效地获取小于size_t的结构的哈希

vmpqdwk3  于 2023-05-30  发布在  其他
关注(0)|答案(3)|浏览(121)

我有一个结构体,它由五个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;
    }
};
}
oalqel3c

oalqel3c1#

所提出的解决方案倾向于未定义的行为,至少是因为memptr可能不满足size_t的对齐要求。
更好的替代方法是使用memcpy

#include<algorithm>  // std::min

    size_t operator()(const MyStruct &s) const
    {
        size_t result = 0;
        memcpy(&result, &s, std::min(sizeof(s), sizeof(size_t));
        return result;
    }

不管结构体和size_t之间的大小差异如何,这都应该起作用,但当然只会区分前sizeof(size_t)字节上的两个结构体。
这对你的结构体来说应该不是问题,但是通常,你必须意识到一个结构体可能包含padding bytes,这些padding bytes具有不受控制的值,这些值可能会扰乱哈希结果。

fdbelqdn

fdbelqdn2#

您需要该类型作为标准无序容器的键,并且它的大小小于std::size_t。因此,位模式可以用作完美散列函数。你不需要奇怪的技术:

std::size_t hash_res = 0;
for(auto byte:
         std::to_array<std::uint8_t>
         ({s.v1, s.v2, s.v3, s.v4, s.v5}))
    (hash_res<<=8)+=byte;

如果编译器不能优化它,更复杂的版本将是:

auto const hash_res=
     std::bit_cast<std::size_t>
     (std::array<std::uint8_t, sizeof(std::size_t)>
     {s.v1, s.v2, s.v3, s.v4, s.v5});

总结一下:

return std::hash<std::size_t>{}(hash_res);

这将修改结果的情况下std::hash内置积分是任何以外的单位。如果您更喜欢完美散列,则可以跳过作为整数的重散列,以避免可能导致冲突概率的截断。

jobtbby3

jobtbby33#

我可以只添加三个额外的字节到结构体,以填补完整的64位,并将结构体转换为size_t,以获得安全的哈希?
否-正如其他人所提到的,由于MyStruct可能具有与size_t不同的对齐方式,并且由于别名(您只能安全地通过char*unsigned char*std::byte*reinterpret_castsize_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将填充字节移动到不太重要的位位置,则它们不会对随机化/分散您的桶使用做出丝毫贡献。
虽然首先使用bitcastMyStruct生成size_t值是合理的,但您可能希望随后对其执行一些实际的、有意义的散列。如前所述,您通常不能简单地在其上调用std::hash<size_t>(),因为这通常是一个身份散列。因此,找到一个SO问题或引用,其中包含size_t的适当散列,或者使用类似Intel CRC指令_mm_crc32_u64的东西。
(因为这些事情很棘手,实现选择有时令人惊讶,当你有理由关心性能时,通常最好用你的数据和哈希函数来测量冲突链长度,以确保你没有意外的冲突率。

相关问题