c++ - 对 std::unordered_map 中使用的 std::array 进行哈希处理

Question

关于在 std::unordered_map 中使用自定义哈希函数，我有一个非常奇怪的问题。

我的key类型比int64大，所以我用std::array来表示。为了获取它的哈希值，我创建了一个 MyHash 类:

class MyHash
{
public:
    std::size_t operator()(const std::array<char, 12>& oid) const
    {
        Convert t;
        std::memcpy(t.arr, oid.data(), 12);
        std::cout << t.a <<" "<<t.b << std::endl;
        return (std::hash<std::int32_t>()(t.a) ^ (std::hash<std::int64_t>()(t.b) << 1)) >> 1;
    }
    union Convert {
        struct {
            std::int32_t a;
            std::int64_t b;
        };
        char arr[12];
    };
};

首先，测试一下:

std::array<char, 12> arr = {1,2,3,4,5,6,7,8,9,10,11,12};
MyHash o;
o(arr);
o(arr);

没关系。它打印相同的 t.a 和 t.b。现在将它与 std::unordered_map 一起使用:

std::unordered_map<std::array<char, 12>, int, MyHash> map;
std::array<char, 12> arr = {1,2,3,4,5,6,7,8,9,10,11,12};
map.insert(std::make_pair(arr, 1));
auto it = map.find(arr);
if(it == map.end())
    std::cout << "error";
else
    std::cout << it->second;

现在会打印error，原因是insert和find中的t.b不一样。这只发生在 vs Release模式(或 g++ O2)

Answer 1

为避免未定义的行为、打包和对齐问题，您可以复制到单个整数:

#include <cstdint>
#include <cstring>
#include <array>

std::size_t array_hash(const std::array<char, 12>& array) {
    std::uint64_t u64;
    std::memcpy(&u64, array.data(), 8);
    std::uint32_t u32;
    std::memcpy(&u32, array.data() + 8, 4);
    // return (std::hash<std::uint32_t>()(u32) ^ (std::hash<std::uint64_t>()(u64) << 1)) >> 1;;
    return u64 + u32; // for simplicity
}

std::size_t uint_hash(std::uint64_t u64, std::uint32_t u32) {
    // return (std::hash<std::uint32_t>()(u32) ^ (std::hash<std::uint64_t>()(u64) << 1)) >> 1;;
    return u64 + u32; // for simplicity
}

使用(g++ 版本 4.8.4)g++ -S --std=c++11 -O3 你会得到:

_Z10array_hashRKSt5arrayIcLm24EE:
.LFB914:
        .cfi_startproc
        movl    8(%rdi), %eax
        addq    (%rdi), %rax
        ret
        .cfi_endproc

和

_Z9uint_hashmj:
.LFB915:
        .cfi_startproc
        movl    %esi, %eax
        addq    %rdi, %rax
        ret
        .cfi_endproc

...这是相当理想的。

另请参阅:Type Punning, Strict Aliasing, and Optimization