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

Question

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

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

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 中的t.b 与find 不同。这只发生在 vs 释放模式（或 g++ O2）

Answer 1

让我们看看这个

  union Convert {
        struct {
            std::int32_t a;
            std::int64_t b;
        };
        char arr[12];
    };

编译器可能会打包 a 和 b 之间的额外字节。因此，通过 char 数组进行双关语的类型不一定会覆盖 struct 部分。类型双关也是 C++ 中的边缘未定义行为；虽然我认为你在这个特定情况下没问题。

发布版本的打包安排似乎与调试版本不同。

许多编译器允许您指定打包安排（#pragma pack？），但如果我是您，我不会依赖它，因为它破坏了编译器的优化策略，而且本质上也是非标准的 C++。

Answer 2

这有点难，但您可以尝试一下，看看它是如何工作的：

struct MyHash {
    std::size_t operator()(const std::array<char, 12>& oid) const {
        auto d = reinterpret_cast<const std::uint32_t*>(oid.data());
        std::size_t prime = 31;
        std::size_t other_prime = 59;
        return d[2] + other_prime*(d[1] + prime*d[0]);
    }
};

请注意，这仅适用于 12 是 sizeof(uint32_t) 的倍数。如果尺寸发生变化，您将不得不进行调整。

Answer 3

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

#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

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

Hash an std::array which used in std::unordered_map

c++

hash

unordered-map