为了能够将std::unordered_map(或其他无序关联容器之一)与用户定义的键类型一起使用，你需要定义两个东西:

A hash function; this must be a class that overrides operator() and calculates the hash value given an object of the key-type. One particularly straight-forward way of doing this is to specialize the std::hash template for your key-type. A comparison function for equality; this is required because the hash cannot rely on the fact that the hash function will always provide a unique hash value for every distinct key (i.e., it needs to be able to deal with collisions), so it needs a way to compare two given keys for an exact match. You can implement this either as a class that overrides operator(), or as a specialization of std::equal, or – easiest of all – by overloading operator==() for your key type (as you did already).

使用哈希函数的困难在于，如果您的键类型由多个成员组成，您通常会让哈希函数计算单个成员的哈希值，然后以某种方式将它们组合成整个对象的一个哈希值。为了获得良好的性能(例如，减少冲突)，您应该仔细考虑如何组合各个哈希值，以确保您避免太频繁地为不同对象获得相同的输出。

哈希函数的一个相当好的起点是使用位移位和按位XOR来组合各个哈希值。例如，假设键类型是这样的:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

下面是一个简单的哈希函数(改编自cppreference例子中使用的用户定义哈希函数):

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

有了这些，你可以为键类型实例化一个std::unordered_map:

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

它将自动使用std::hash<Key>作为上面定义的哈希值计算，并将operator==定义为Key的成员函数用于相等性检查。

如果你不想在std命名空间中专门化模板(尽管在这种情况下是完全合法的)，你可以将哈希函数定义为一个单独的类，并将其添加到map的模板参数列表中:

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

如何定义一个更好的哈希函数?如上所述，定义一个好的哈希函数对于避免冲突和获得良好的性能很重要。对于一个真正的好模型，你需要考虑所有字段的可能值的分布，并定义一个散列函数，将该分布投射到一个尽可能宽且均匀分布的可能结果空间。

这可能很难;上面的异或/位移位方法可能是一个不错的开始。为了更好地开始，您可以使用Boost库中的hash_value和hash_combine函数模板。前者的作用类似于标准类型的std::hash(最近还包括元组和其他有用的标准类型);后者帮助您将单个哈希值合并为一个哈希值。下面是使用Boost辅助函数的哈希函数的重写:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

下面是一个没有使用boost的重写，但使用了很好的组合哈希的方法:

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            size_t res = 17;
            res = res * 31 + hash<string>()( k.first );
            res = res * 31 + hash<string>()( k.second );
            res = res * 31 + hash<int>()( k.third );
            return res;
        }
    };
}

我认为，jogojapan给出了一个非常好的详尽的答案。在阅读我的文章之前，你绝对应该看看它。但是，我想补充以下几点:

可以为unordered_map单独定义比较函数，而不是使用相等比较操作符(operator==)。这可能很有帮助，例如，如果您想使用后者来比较两个Node对象的所有成员，而只是将某些特定成员作为unordered_map的键。 您也可以使用lambda表达式来代替定义散列和比较函数。

总之，对于Node类，代码可以这样写:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

注:

我只是在jogojapan的回答的最后重用了哈希方法，但是你可以在这里找到一个更通用的解决方案(如果你不想使用Boost)。 我的代码可能有点太小了。要获得可读性稍强的版本，请参阅Ideone上的代码。

对于枚举类型，我认为这是一种合适的方式，与类之间的区别是如何计算哈希值。

template <typename T>
struct EnumTypeHash {
  std::size_t operator()(const T& type) const {
    return static_cast<std::size_t>(type);
  }
};

enum MyEnum {};
class MyValue {};

std::unordered_map<MyEnum, MyValue, EnumTypeHash<MyEnum>> map_;

使用自定义类作为unordered_map(稀疏矩阵的基本实现)的键的最基本的可能复制/粘贴完整可运行的例子:

// UnorderedMapObjectAsKey.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

struct Pos
{
  int row;
  int col;

  Pos() { }
  Pos(int row, int col)
  {
    this->row = row;
    this->col = col;
  }

  bool operator==(const Pos& otherPos) const
  {
    if (this->row == otherPos.row && this->col == otherPos.col) return true;
    else return false;
  }

  struct HashFunction
  {
    size_t operator()(const Pos& pos) const
    {
      size_t rowHash = std::hash<int>()(pos.row);
      size_t colHash = std::hash<int>()(pos.col) << 1;
      return rowHash ^ colHash;
    }
  };
};

int main(void)
{
  std::unordered_map<Pos, int, Pos::HashFunction> umap;

  // at row 1, col 2, set value to 5
  umap[Pos(1, 2)] = 5;

  // at row 3, col 4, set value to 10
  umap[Pos(3, 4)] = 10;

  // print the umap
  std::cout << "\n";
  for (auto& element : umap)
  {
    std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
  }
  std::cout << "\n";

  return 0;
}

查看以下链接https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/了解更多详细信息。

自定义类必须实现==运算符 必须为类创建一个哈希函数(对于int等基本类型和string等类型，哈希函数是预定义的)

STL不为pair提供hash函数。您需要自己实现它，并指定为模板参数或将其放入命名空间std中，从那里将自动获取它。遵循https://github.com/HowardHinnant/hash_append/blob/master/n3876.h对于实现结构的自定义哈希函数非常有用。更多的细节在这个问题的其他答案中有很好的解释，所以我不会重复。Boost中也有类似的东西(hash_combine)。

The answers here were quite helpful, but I still struggled mightily trying to figure this out, so perhaps my lessons learned will be beneficial. I had a bit of a unique situation compared to the OP; my key was a custom UUID class that I didn't own. In what I consider a bug/oversight, this class did not define a hash function, or overload for operator() (it did define the operator==, so I was set there). Yes, I had the source, but it was widely distributed and controlled, so modifying it was a non-starter. I wanted to use this UUID as key in a std::unordered_map member, like

std::unordered_map<UUID, MyObject> mapOfObjs_;

在Visual Studio中，我最终确定了这个解决方案:

// file MyClass.h

namespace myNamespace
{
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // XORed the most and least significant bits, not important
   }
   ... 
   class MyClass
   {
      ...
   private:
      std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

这在Windows上运行得很好。然而，当我最终将我的代码带到linux中的gcc时，我得到了警告(释义)

'MyClass'有一个字段'mapOfObjs_'，其类型使用匿名命名空间

我甚至得到了这个警告与所有警告禁用，所以gcc必须考虑它相当严重。我搜索了一下，找到了这个答案，这表明我需要将散列函数代码移到.cpp文件中。

在这一点上，我还尝试从UUID类派生:

// file MyClass.h

namespace myNamespace
{
   struct myUuid : public UUID
   {
      // overload the operator()
   };
   ...
   // and change my map to use this type
   std::unordered_map<myUuid, std::unique_ptr<MyObject>> mapOfObjs_;
}

然而，这也带来了一系列问题。也就是说，使用(现在的父)UUID类的代码的所有部分都与我的映射不兼容，如:

void MyClass::FindUuid(const UUID& id)
{
   // doesn't work, can't convert `id` to a `myUuid` type
   auto it = mapOfObjs_.find(id);
   ...
}

现在已经坏了。我不想更改所有的代码，所以我放弃了，回到了“将代码放在.cpp文件中”的解决方案。然而，我仍然固执地尝试了一些事情来保留.h文件中的哈希函数。我真正想避免的是从哈希函数定义中删除auto，因为我不知道，也不想弄清楚它的类型是什么。所以我试着:

class MyClass
{
   ...
private:
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // my hash function
   }
};

但是这个(或这个的变体)返回错误，比如“不能在类中有静态初始化器”，“不能在这里使用auto”，等等(我有一个硬的c++ 11要求)。所以我最终接受了我需要像对待静态变量一样对待它，在头文件中声明它，并在.cpp文件中初始化它。一旦我搞清楚了它的类型，它就直截了当了:

// MyClass.h
namespace myNamespace
{
   class MyClass
   {
      ...
   private:
      static std::function<unsigned long long(const UUID&)> staticUuidHashFunc;

      std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

最后在。cpp文件中:

// MyClass.cpp

namespace myNamespace
{
   std::function<unsigned long long(const UUID&)> MyClass::staticUuidHashFunc = [](const UUID& n)
    {
        // the hash function
    };

    MyClass::MyClass()
       : mapOfObjs_{ std::unordered_map<UUID, std::unique_ptr<MyObject>, decltype(staticUuidHashFunc)> (MyClass::NUMBER_OF_MAP_BUCKETS, staticUuidHashFunc)}
    {  }

   ...
}

在.cpp文件中定义静态哈希函数是关键。在那之后，Visual Studio和gcc都很高兴。