6バイトのフィールドからハッシュを計算しますか？

Question

私は、std::unordered_mapのために使用できるように6バイトのフィールドをハッシュする効率的な方法を探しています。

私は、これはハッシュを作成する従来の方法だろうと思う：

struct Hash { 
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const { 
     std::size_t key = 0; 
     boost::hash_combine(key, mac[0]); 
     boost::hash_combine(key, mac[1]); 
     boost::hash_combine(key, mac[2]); 
     boost::hash_combine(key, mac[3]); 
     boost::hash_combine(key, mac[4]); 
     boost::hash_combine(key, mac[5]); 
     return key; 
    } 
}; 

しかし、私はこのトリックを使用して（〜20％）私はそれが少し速く作ることができることに気づいた。

struct Hash { 
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const { 
     std::size_t key = 0; 

     // Possibly UB? 
     boost::hash_combine(key, reinterpret_cast<const uint32_t&>(mac[0])); 
     boost::hash_combine(key, reinterpret_cast<const uint16_t&>(mac[4])); 
     return key; 
    } 
}; 

そして、これはより速くだった：

struct Hash { 
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const { 
     // Requires size_t to be 64-bit. 
     static_assert(sizeof(std::size_t) >= 6, "MAC address doesn't fit in std::size_t!"); 

     std::size_t key = 0; 

     // Likely UB? 
     boost::hash_combine(key, 0x0000FFFFFFFFFFFF & reinterpret_cast<const uint64_t&>(mac[0])); 
     return key; 
    } 
}; 

私の質問は二つある：

1. UBではこれらの最適化が行われますか？
2. 私の最初の解決方法はありますか？それとも良い方法がありますか？

Answer 1

最適化によって厳密なエイリアシングルールが破られています。これは、（標準的に言えば）未定義の動作につながります。

最終的な最適化は、あなたが本質的に読まなければならないメモリを読んでいるので、私が一番心配しています。このメモリが保護された場合、トラップを引き起こす可能性があります。

boost::hash_rangeを使用していない理由はありますか？

---

boost::hash_rangeが必要なほど高速ではないことが判明したので、私はエイリアシングに基づいて別のソリューションを提案します。むしろ、1つのソリューションに2つのソリューションがあります。

最初のアイデアは、char*を一時的なタイプとして使用してエイリアシングを抑制できることです。

size_t key = 0; 
char* k = &reinterpret_cast<char*>(&key); 

std::copy(mac.begin(), mac.end(), k); 

return key; 

は、有効なハッシュの実装です。

しかし、もう少し先に進むことができます。アライメントとパディングのために、char[6]とchar[8]の格納は、マップノード内で同じ量のメモリを使用する可能性があります。したがって、我々はunionを使用することにより、に種類を豊かにできます

union MacType { 
    unsigned char value[8]; 
    size_t hash; 
}; 

を今、あなたは適切にクラス内でこれをカプセル化（とあなたが常にバイト7と0から8を初期化することを確認してください）、および実装することができますあなたが実際に必要とするstd::array<unsigned char, 6>のインターフェイス。

私はハッシュと高速（非英字）の比較のために、小さな文字列（8文字以下）に同様のトリックを使用しました。