Hash a std :: array, который используется в std :: unordered_map

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

Это нормально. Он печатает те же t.a и t.b. Теперь используйте его с станд :: 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 в вставке отличается с находкой. И это только произойдет в режиме выпуска против (или г ++ 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 
} 

С (г ++ версии 4.8.4) г ++ -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

Давайте посмотрим на этот

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

Компилятор может также пакет дополнительные байты между a и b. Таким образом, тип, выполняющий кастинг через массив char, не обязательно будет накладывать часть struct. Тип punning также является пограничным неопределенным поведением в 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) виду вас. Если изменения размера вам придется корректировать.