std :: unordered_mapで使用されるstd :: arrayをハッシュします。

Question

std :: unordered_mapで自己定義されたハッシュ関数を使用することについて、私は非常に奇妙な問題があります。

私のキータイプは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); 

それはOKです。それは同じ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は検索と異なるです。そして、これだけリリースモード（または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

Answer 2

はaとbの間かもしれないだけでなくパック余分なバイトコンパイラのは、この

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

を見てみましょう。そのため、char配列をペイントするタイプは、必ずstructの一部をオーバーレイするとは限りません。型打ちは、C++での境界線の未定義動作です。私はだと思いますが、あなたはこの特定の例では大丈夫です。

リリースビルドの梱包方法は、デバッグビルドとは異なるようです。

多くのコンパイラでは、梱包の手配（#pragma pack？）を指定することができますが、コンパイラの最適化戦略を破っており、本質的に非標準のC++であるため、私はあなたであったとしても頼りません。

Answer 3

これはハックのビットですが、あなたはそれを試してみて、それがどのように動作するかを見ることができる：

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)あなたの心の倍数であるため。サイズが変わった場合は、調整する必要があります。あなたは、個々の整数にコピーすることが未定義の動作を避けるために