c++ - 从 6 字节字段计算散列？

Question

我正在寻找一种对 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;
    }
};

我的问题有两个方面:

1. 这些优化会导致 UB 吗？
2. 我的第一个解决方案可行吗？或者有更好的方法吗？

Answer 1

您的优化违反了严格的别名规则，这会导致(按标准来说)未定义的行为。

最后的优化最让我担心，因为您本质上是在读取不应该读取的内存，如果该内存恰好受到保护，这可能会引发陷阱。

您不使用 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]很可能在 map 节点中使用相同数量的内存。因此，我们可以使用 union 来丰富类型。 :

union MacType {
    unsigned char value[8];
    size_t hash;
};

现在，您可以将其适本地封装在一个类中(并确保始终将字节 7 和 8 初始化为 0 )，并实现 std::array<unsigned char, 6> 的接口(interface)你真正需要的。

我对小字符串(8 个字符以下)使用了类似的技巧来进行散列和快速(非字母)比较，这真的很不错。