unordered_map 自定义哈希_unorderedmap 自定义哈希函数

unordered_map定义

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;
    > class unordered_map
1
2
3
4
5
6
7

• 第1个参数，存储key值。

• 第2个参数，存储mapped value。

• 第3个参数，为哈希函数的函数对象。它将key作为参数，并利用函数对象中的哈希函数返回类型为size_t的唯一哈希值。默认值为std::hash< key>。

• 第4个参数，为等比函数的函数对象。它内部通过等比操作符’=='来判断两个key是否相等，返回值为bool类型。默认值是std::equal_to< key>。
  
  

原理分析

对于unordered_map而言，当我们插入<key, value>的时候，需要哈希函数的函数对象对key进行hash，又要利用等比函数的函数对象确保插入的键值对没有重复。然而，当我们自定义类型时，c++标准库并没有对应的哈希函数和等比函数的函数对象。因此需要分别对它们进行定义。

因为都是函数对象，它们两个的实际定义方法并没有很大差别。不过后者比前者多了一个方法。因为等比函数的函数对象默认值std::equal_to<key>内部是通过调用操作符"=="进行等值判断，因此我们可以直接在自定义类里面进行operator==()重载（成员和友元都可以）。

因此，如果要将自定义类型作为unordered_map的键值，需如下两个步骤：

1. 定义自定义key的哈希函数的函数对象；

2. 定义等比函数的函数对象或者在自定义类里重载operator==()。

【PS】如果自定义类的数据成员为私有，则哈希函数对象需要被声明为自定义类的友元。

方法

#include <bits/stdc++.h>
using namespace std;

class Person {
public:
    string name;
    int age;
	friend struct hash_name;//应对成员变量为私有情况
    Person(string n, int a) {
        name = n;
        age = a;
    }

    bool operator==(const Person& p) const {
        return name == p.name && age == p.age;
    }
};

struct hash_name {//公有成员
    size_t operator()(const Person& p) const {//别忘记const
        return hash<string>()(p.name) ^ hash<int>()(p.age);
    }
};
struct equal_person{
    bool operator()(const Person&a,const Person&b) const{
        return a.name==b.name && a.age==b.age;
    }
};

int main() {
    unordered_map<Person, int, hash_name> ids;  
    unordered_map<Person, int, hash_name,equal_person> ids;  //不需要重载operator==写法
    ids[Person("Mark", 17)] = 40561;
    ids[Person("Andrew", 16)] = 40562;
    for (auto ii = ids.begin(); ii != ids.end(); ii++)
        cout << ii->first.name << " " << ii->first.age << " : " << ii->second
             << endl;
    getchar();
    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
33
34
35
36
37
38
39
40
41
42

hash<T>

STL库的哈希函数对象除了字符串类型外只是返回原值，不适用于任何情况，有时需要自己定义哈希函数。

#define _Cxx_hashtable_define_trivial_hash(_Tp) 	\
  template<>						\
    struct hash<_Tp> : public __hash_base<size_t, _Tp>  \
    {                                                   \
      size_t                                            \
      operator()(_Tp __val) const noexcept              \
      { return static_cast<size_t>(__val); }            \
    };
1
2
3
4
5
6
7
8

字符串类型：

转自：
https://blog.csdn.net/y109y/article/details/82669620