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 이후

---

최대한 빨리 할 필요에 따라, 내가 앨리어싱에 따라 다른 해결책을 제안 할 수 없습니다 밝혀졌습니다. 오히려 하나의 솔루션이 두 개 있습니다.

첫 번째 아이디어는 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 문자 미만)에 비슷한 트릭을 사용했으며 정말 멋졌습니다.