1

たとえば、次の構造体では:

1) editLine は CLRF を持つデータ行へのポインター、
2) nDisplayLine はこの editLine の表示行インデックス、
3) start は表示行のオフセット、
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_

問題は、この構造のハッシュ関数をどのように設計するかです。ガイドラインはありますか?

ハッシュ関数に衝突がないことを確認するにはどうすればよいですか?

4

1 に答える 1

2

ハッシュ関数を作成するには、整数に対して定義されているstd::hashを使用できます。次に、ここで説明されているように、「ブースト担当者が行うように」(適切なハッシュを行うことは簡単ではないため)、それらを組み合わせることができます: http://en.cppreference.com/w/cpp/utility/hash。

これは hash_combine メソッドです:

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

したがって、「ガイドライン」は多かれ少なかれ cppreference に示されているものです。

ハッシュ関数に衝突がないことを確認できません。衝突がないということは、データを失わないことを意味します (または、クラスの可能性の小さなセットに自分自身を制限します)。各フィールドに任意の int32 値が許可されている場合、衝突のないハッシュは非常に大きなインデックスになり、小さなテーブルには収まりません。unordered_map に衝突を処理させ、上記で説明したように std::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;
}

次に、クラスの std::hash 演算子を特殊化できます。

namespace std
{
    template<>
    struct hash<CacheKey>
    {
    public:
        std::size_t operator()(CacheKey const& s) const 
        {
            return s.hash();
         }
    };
}
于 2013-07-01T11:43:26.037 に答える