STL-unordered系列容器自定义哈希函数

概述:

由于在STL中,有关于hash的数据结构值针对于基础数据类型如int, string等提供了hash模板,
因此如果想要使用自定义类,那么我们需要自定义hash函数!

重写hash函数和equal_to函数

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

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class A {
public:
uint32_t a = 1;
string b = "aaa";
};


template<>
struct std::hash<A> {
std::size_t operator()(const A& p) const {
std::size_t h1 = std::hash<uint32_t>()(p.a);
std::size_t h2 = std::hash<string>()(p.b);
return h1 ^ h2;
}
};
template<>
struct std::equal_to<A> {
bool operator()(const A& lhs, const A& rhs) const {
return lhs.a == rhs.a && lhs.b == rhs.b;
}
};


int main(int argv, char** argc){
A a, b;
unordered_set<A> tempSet = { a,b };
unordered_map<A, int> tempMap = { {a,1},{b,2} };
system("pause");
}

效率

map与unordered_map的int类型测试

插入范围 查询范围 map插入 map查询 unordered_map插入 unordered_map查询
100 100 0ms 0ms 1ms 0ms
1000 1000 1ms 1ms 1ms 0ms
10000 10000 8ms 7ms 15ms 5ms
100000 100000 70ms 58ms 92ms 20ms
1000000 1000000 588ms 532ms 688ms 118ms

set与unordered_set的int类型测试

插入范围 查询范围 set插入 set查询 unordered_set插入 unordered_set查询
100 100 0ms 0ms 1ms 0ms
1000 1000 1ms 1ms 2ms 0ms
10000 10000 8ms 6ms 13ms 3ms
100000 100000 80ms 60ms 109ms 33ms
1000000 1000000 807ms 599ms 945ms 327ms

结论

数据量小于100或者查询次数小于插入次数没必要使用unordered容器

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!