哈希一个std :: array在std :: unordered_map中使用

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

我的密钥类型大于INT64，因此我使用std ::数组来表示它。为了获得哈希值，我创建了一个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，原因是插入中的t.b与查找不同。这只有在VS发布模式（或G O2）

中发生

为了避免不确定的行为，包装和对齐问题，您可以复制各个整数：

#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 -SSTD = 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

...这是相当最佳的。

另请参见：键入双关，严格的混叠和优化

让我们看一下这个

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

编译器可以很好地 pack a和 b之间的额外字节。因此，通过char阵列进行的pun类型不一定会覆盖struct部分。类型的双关语也是C 中的边界不确定的行为；尽管我 think 在此特定实例中您还可以。

看来，发行版的包装布置与调试构建不同。

许多编译器允许您指定包装安排（#pragma pack？），但是如果我是您，我不会依靠它，因为它会击败编译器的优化策略，并且本质上也是非标准的C 。

这有点黑客，但是您可以尝试并查看其工作原理：

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)的倍数。如果大小变化，则必须调整。

相关内容

最新更新

热门标签：