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 回答