我正在寻找一种有效的方法来对 6 字节字段进行哈希处理,以便将其用于 std::unordered_map
。
我认为这将是创建哈希的传统方法:
struct Hash {
std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
std::size_t key = 0;
boost::hash_combine(key, mac[0]);
boost::hash_combine(key, mac[1]);
boost::hash_combine(key, mac[2]);
boost::hash_combine(key, mac[3]);
boost::hash_combine(key, mac[4]);
boost::hash_combine(key, mac[5]);
return key;
}
};
但是我注意到使用这个技巧我可以让它更快一点(~20%):
struct Hash {
std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
std::size_t key = 0;
// Possibly UB?
boost::hash_combine(key, reinterpret_cast<const uint32_t&>(mac[0]));
boost::hash_combine(key, reinterpret_cast<const uint16_t&>(mac[4]));
return key;
}
};
这甚至更快:
struct Hash {
std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
// Requires size_t to be 64-bit.
static_assert(sizeof(std::size_t) >= 6, "MAC address doesn't fit in std::size_t!");
std::size_t key = 0;
// Likely UB?
boost::hash_combine(key, 0x0000FFFFFFFFFFFF & reinterpret_cast<const uint64_t&>(mac[0]));
return key;
}
};
我的问题有两个:
- 这些优化会带来 UB 吗?
- 我的第一个解决方案是可行的方法吗?或者有更好的办法吗?
最佳答案
您的优化违反了严格的别名规则,这会导致(标准而言)未定义的行为。
最后一个优化最让我担心,因为您本质上是在读取不应该读取的内存,如果该内存碰巧受到保护,这可能会引发陷阱。
您不使用 boost::hash_range
的任何原因?
自 boost::hash_range
结果没有达到要求的那么快,我会提出另一种基于别名的解决方案。或者更确切地说,两种解决方案合二为一。
第一个想法是可以使用char*
来抑制锯齿。作为临时类型。
size_t key = 0;
char* k = &reinterpret_cast<char*>(&key);
std::copy(mac.begin(), mac.end(), k);
return key;
因此是哈希的有效实现。
但是,我们可以更进一步。由于对齐和填充,存储 char[6]
和char[8]
可能在映射节点内使用相同数量的内存。因此,我们可以通过使用 union
来丰富类型。 :
union MacType {
unsigned char value[8];
size_t hash;
};
现在,您可以将其正确封装在一个类中(并确保始终将字节 7
和 8
初始化为 0
),并实现 std::array<unsigned char, 6>
的接口(interface)您真正需要的。
我对小字符串(低于 8 个字符)使用了类似的技巧来进行散列和快速(非字母)比较,这真的很不错。
关于c++ - 从 6 字节字段计算哈希值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10564380/