一对整数的哈希函数出现错误

Question

一对整数的哈希函数出现错误

40

我有以下一个类，其中包含一个unordered_map成员，并且定义了一个用于pair<int,int>类型的哈希函数。

class abc
{public :
    unordered_map < pair<int,int> , int > rules ;
    unsigned nodes;
    unsigned packet ;     
};

namespace std {
template <>
    class hash < std::pair< int,int> >{
    public :
        size_t operator()(const pair< int, int> &x ) const
        {
            size_t h =   std::hash<int>()(x.first) ^ std::hash<int>()(x.second);
            return  h ;
        }
    };
}

但是我收到了以下错误：

error: invalid use of incomplete type ‘struct std::hash<std::pair<int, int> >

error: declaration of ‘struct std::hash<std::pair<int, int> >

error: type ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>’ is not a direct base of ‘std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’

- Shambo

1

你应该前向声明 template<typename T> class hash;。 - Rapptz

1

@Rapptz：仅有前向声明是不够的。在“class abc”之前，OP需要定义特化。 - Jesse Good

@JesseGood 是的，我现在也看到了。 - Rapptz

如果两个程序员在同一程序的两个组件中尝试这样做，会发生什么？ - curiousguy

2个回答

4

我更喜欢依赖于 std::hash<uintmax_t> 的标准实现来混合一个 std::pair 组件的哈希值：

#include <functional>
#include <utility>

struct hash_pair final {
    template<class TFirst, class TSecond>
    size_t operator()(const std::pair<TFirst, TSecond>& p) const noexcept {
        uintmax_t hash = std::hash<TFirst>{}(p.first);
        hash <<= sizeof(uintmax_t) * 4;
        hash ^= std::hash<TSecond>{}(p.second);
        return std::hash<uintmax_t>{}(hash);
    }
};

- Vladimir Reshetnikov

hash <<= sizeof(uintmax_t) * 4; 这样做不会完全删除哈希吗？例如，假设 uintmax 有 64 位。将其左移（4*64）位将超出其限制。 - Konchog

sizeof返回字节数，但<<需要指定要移位的位数。https://en.cppreference.com/w/cpp/language/sizeof - Vladimir Reshetnikov

谢谢 Vlad。我忘记了它是以字节而不是位为单位测量的。因此，目的是将第一个哈希精确地移动TFirst大小的一半。旋转哈希那么多位是否更好？否则，我们会失去第一个哈希的一半位。 - Konchog

这个（例如 uintmax_t）会编译成 rol 32：hash = (hash << (sizeof(uintmax_t) << 2)) | (hash >> (sizeof(uintmax_t)) << 2)); - Konchog

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Casey · Accepted Answer

很遗憾，此程序具有未定义的行为。 C++11 §17.6.4.2.1：

一个程序可以在命名空间std中添加任何标准库模板的模板特化，但前提是该声明依赖于用户定义类型，并且该特化满足原始模板的标准库要求且未被明确禁止。

hash>依赖于基本和标准库类型。这很容易通过在namespace std之外定义您的哈希类，并在map声明中显式使用该哈希来解决：

struct pairhash {
public:
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const
  {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};

class abc {
  std::unordered_map<std::pair<int,int>, int, pairhash> rules;
};

编辑：我在这里使用异或（xor）来组合一对成员的哈希值，因为我很懒，但为了严肃使用，异或是一种相当糟糕的哈希组合函数。