0

我只想使用我的结构作为键的 unordered_map，因为我不需要任何排序..但我无法找到自己拥有所有这些哈希的东西..

作为一个相关的问题..当人们比较无序和有序映射时，他们从不谈论哈希函数，那怎么可能？一个糟糕的哈希函数不能让无序映射比映射慢吗？（仅由于散列函数）

struct exemple{

  unsigned char a,b,c;
  unsigned int n;

  bool operator == ( const exemple & other) const {..}
};

namespace std {
template <>
struct hash<exemple> : public std::unary_function<const exemple &, std::size_t>
{
    inline std::size_t operator()(const exemple & exemple_p ) const
    {
        return 0;// what do I do
    }
};

}

-edit- a,b,c 只能有值 'a', 'b', 'c' 或 'd', n 在 3 到 60 之间变化。

4

4 回答 4

4

您在散列函数中所做的事情取决于您获得的值，不一定取决于它们的类型。如果所有四个数据成员包含均匀分布的每个值，我会将这两个字符组合成一个unsigned long并返回两个值异或的结果：

typedef unsigned long ulong;
return n ^ (ulong(a << 16) | ulong(b << 8) | ulong(c));

它当然是一个哈希函数。它是否运作良好是一个不同的问题。您也可以将结果与std::hash<unsigned long>.

于 2012-11-15T00:26:12.337 回答
2

这是一个基线哈希函数：

unsigned long long h = (n << 24) | (a << 16) | (b << 8) | c;
return std::hash(h);

即，只需将成员打包到一个unsigned long long中，然后将工作卸载到std::hash. int在32 位宽和64 位的常见情况下，long long假设您的字符不是负数，这会将对象中的所有信息用于哈希。

于 2012-11-15T00:24:18.000 回答
2

将您struct作为一个整体考虑为一串字节（准确地说是 7 个）。您可以对这 7 个字节使用任何可接受的通用字符串散列函数。这是应用于您的示例的 FNV（Fowler/Noll/Vo）通用位串哈希函数（在给定的哈希函子类中）：

inline std::size_t operator()(const exemple& obj ) const
{
  const unsigned char* p = reinterpret_cast<const unsigned char*>( &obj );
  std::size_t h = 2166136261;

  for (unsigned int i = 0; i < sizeof(obj); ++i)
    h = (h * 16777619) ^ p[i];

  return h;
}

请注意我如何将对exemple结构 ( obj) 的引用转换为指向的指针，const unsigned char以便我可以一个接一个地访问结构的字节，并将其视为不透明的二进制对象。请注意，sizeof(obj)实际上可能是 8 而不是 7，具体取决于编译器的填充（这意味着结构中的某处有一个垃圾填充字节，可能介于c和之间n。如果需要，可以重写散列函数以遍历a、b和c然后按顺序（或任何顺序）的字节n，这将消除任何填充字节（可能存在或可能不存在）对您的struct.

是的，一个糟糕的哈希函数可能会unordered_map比ordered_map. 这并不总是被讨论，因为像上面给出的 FNV 哈希这样的通用快速算法被假定为那些使用 的人使用unordered_map，并且在这些情况下，通常 aunordered_map比 a 更快ordered_map，代价是迭代容器元素的能力为了。但是，是的，您必须对数据使用良好的散列函数，并且通常使用这些众所周知的散列之一就足够了。然而，最终，每个散列函数都有其弱点，具体取决于输入数据（这里是exemple结构的内容）的分布。

可以在Eternally Confuzzled中找到关于广义散列和示例散列函数的一个很好的讨论，包括一个类似于我给你的 C 风格的 FNV 散列。

于 2012-11-15T01:03:04.973 回答
1

boost::hash_combine专为此目的而设计：

std::size_t hash = 0;
for (const auto& value : {a, b, c}) {
    boost::hash_combine(hash, value);
}
boost::hash_combine(hash, n);
return hash;
于 2018-04-11T19:33:12.373 回答