使用 pair 做 unordered_map 的键值

背景

标准库中 unordered_map 是使用哈希表实现的，对于内置类型标准库通过 std::hash 提供了哈希函数的实现，因此若采用非内置类型做键值，则需要程序员自己提供其哈希函数的实现。

用 pair 做键值

①．自定义哈希函数

struct pairHash
{
  template<typename T,typename U>
  size_t operator()(const pair<T, U> & p) const
  {
    return hash<T>()(p.first) ^ hash<U>()(p.second);
  }

  template<typename T, typename U>
  bool operator() (const pair<T, U> & p1, const pair<T, U> & p2) const
{
    return p1.first == p2.first && p1.second == p2.second;
  }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

②．代码示例

unordered_map<pair<int, int>, int, pairHash, pairHash> m;
m[{2, 4}] = 24;
m[{4, 2}] = 42;

cout << m[{2, 4}] << endl;
cout << m[{4, 2}] << endl;
1
2
3
4
5
6

万能哈希函数

①．概述

对于任意自定义类型，我们只需要提供其哈希函数即可作为 unordered_map 的 key 使用。

②．万能哈希函数

template <typename... Types>
size_t hash_val(const Types&... args)const
{
  size_t seed = 0;
  hash_value(seed, args...);
  return seed;
}

template <typename T, typename... Types>
void hash_value(size_t& seed,const T& firstArg,const Types&... args) const
{
  hash_combine(seed, firstArg);
  hash_value(seed, args...);
}

template <typename T>
void hash_value(size_t& seed,const T& val) const
{
  hash_combine(seed, val);
}

template<typename T>
void hash_combine(size_t& seed,const T& val) const
{
  seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

③．代码示例

struct demoStruct
{
  string name;
  int id;
    
  demoStruct( const string & m_name ,int m_id):name(m_name),id(m_id){}
  bool operator == (const demoStruct &demo) const
  {
    return demo.id == id && demo.name == name;
  }
};

class CustomHashDemo
{
public:
  std::size_t operator()(const demoStruct& c) const
  {
    return hash_val(c.name, c.id);
  }
private:
  /*同上*/
};

int main()
{

  unordered_map<demoStruct,int, CustomHashDemo> m;
  m[{"张三", 12}] = 24;
  m[{"李四", 42}] = 42;
    
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32