사용자 정의 유형에 해시 함수를 구성하는 방법은 무엇입니까? 예를 들어

Question

다음 구조체의 경우 :

1) editLine는 CLRF되어있는 데이터 선에 대한 포인터이다
2) nDisplayLine는
3) 시작은 오프셋이 editLine의 표시 라인 인덱스이며 디스플레이 라인에서
4) len은 텍스트의 길이입니다.

struct CacheKey { 
    const CEditLine* editLine; 
    int32 nDisplayLine; 
    int32 start; 
    int32 len; 
    friend bool operator==(const CacheKey& item1, const CacheKey& item2) { 
     return (item1.start == item2.start && item1.len == item2.len && item1.nDisplayLine == item2.nDisplayLine && 
      item1.editLine == item2.editLine); 
    } 
    CacheKey() { 
     editLine = NULL; 
     nDisplayLine = 0; 
     start = 0; 
     len = 0; 
    } 
    CacheKey(const CEditLine* editLine, int32 dispLine, int32 start, int32 len) : 
     editLine(editLine), nDisplayLine(dispLine), start(start), len(len) 
    { 
    } 

    int hash() { 
     return (int)((unsigned char*)editLine - 0x10000) + nDisplayLine * nDisplayLine + start * 2 - len * 1000; 
    } 
}; 

이제 문제는이 구조에 대한 해시 함수를 설계하는 방법입니다 std::unordered_map<int, CacheItem> cacheMap_

에 넣어 필요가있는 가이드 라인이있다?

어떻게 해시 함수가 충돌 없는지 확인할 수 있습니까?

Answer 1

해시 함수를 만들려면 정수로 정의 된 std::hash을 사용할 수 있습니다. 그렇다면 여기에 설명 된대로 "부스트 녀석들이하는 것처럼"(좋은 해시를하는 것이 중요하지 않기 때문에) 그들을 결합 할 수 있습니다 : http://en.cppreference.com/w/cpp/utility/hash.

inline void hash_combine(std::size_t& seed, std::size_t v) 
{ 
    seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

는 그래서 "가이드 라인"cppreference에 표시됩니다 무엇을 더 이하 : 여기

는 hash_combine 방법입니다.

해시 기능을 사용할 수 없는지 확인할 수는 없습니다. 콜리 젼 (collision)을 사용하지 않는다는 것은 데이터를 잃어 버리지 않는다는 것을 의미합니다 (또는 자신의 클래스에 대한 가능성을 제한 할 수 있음). 각 필드에 int32 값이 허용되면 충돌없는 해시는 엄청나게 큰 인덱스이며 작은 테이블에 맞지 않습니다. unordered_map이 충돌을 처리하도록하고 위에서 설명한대로 std :: hash hash를 결합합니다.

당신이 경우, 당신은 당신의 클래스에 대한 표준 : 해시 연산자를 전문으로 할 수 있습니다, 그리고

std::size_t hash() const 
{ 
    std::size_t h1 = std::hash<CEditLine*>()(editLine); 
    //Your int32 type is probably a typedef of a hashable type. Otherwise, 
    // you'll have to static_cast<> it to a type supported by std::hash. 
    std::size_t h2 = std::hash<int32>()(nDisplayLine); 
    std::size_t h3 = std::hash<int32>()(start); 
    std::size_t h4 = std::hash<int32>()(len); 
    std::size_t hash = 0; 
    hash_combine(hash, h1); 
    hash_combine(hash, h2); 
    hash_combine(hash, h3); 
    hash_combine(hash, h4); 
    return hash; 
} 

같이 보일 것입니다.

namespace std 
{ 
    template<> 
    struct hash<CacheKey> 
    { 
    public: 
     std::size_t operator()(CacheKey const& s) const 
     { 
      return s.hash(); 
     } 
    }; 
}