Hash std :: array utilisé dans std :: unordered_map

Question

J'ai un problème très étrange concernant l'utilisation de la fonction de hachage auto-définie dans std :: unordered_map.

Mon type de clé est plus grand que int64, donc j'utilise std :: array pour le représenter. Pour obtenir la valeur de hachage, je crée une classe 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]; 
    }; 
}; 

Tout d'abord, le tester:

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

Il est OK. Il imprime le même t.a et t.b. Maintenant utiliser avec 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; 

Maintenant, il imprimera error, la raison est le t.b en insert est différent avec find. Et cela arrive seulement en mode vs libération (ou g ++ O2)

Answer 1

Pour éviter un comportement non défini, l'emballage et des problèmes d'alignement, vous pouvez copier des entiers individuels:

#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 
} 

Avec (g ++ version 4.8.4) g ++ -S --std = C++ 11 -O3 vous obtenez:

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

et

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

... ce qui est assez optimale.

Voir aussi: Type Punning, Strict Aliasing, and Optimization

Answer 2

Regardons ce

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

Le compilateur peut bien pack octets supplémentaires entre a et b. Donc, le type qui pige par le biais du tableau char ne recouvrira pas nécessairement la partie struct. Le type punning est également un comportement non défini en C++; bien que je pense vous êtes OK dans cette instance particulière.

Il semble que les dispositions d'emballage pour la construction de version diffèrent de la construction de mise au point.

Beaucoup de compilateurs vous permettent de spécifier les arrangements d'emballage (#pragma pack?) Mais je ne compterais pas dessus si j'étais vous puisqu'il bat les stratégies d'optimisation du compilateur et est également essentiellement C++ non-standard.

Answer 3

C'est un peu un hack mais vous pouvez l'essayer et voir comment cela fonctionne:

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]); 
    } 
}; 

Cela ne fonctionne que parce que 12 est un multiple de sizeof(uint32_t) esprit que vous. Si la taille change, vous devrez ajuster.