C++ STL 之哈希表 | unordered_map

C++ STL中,哈希表对应的容器是 unordered_map(since C++ 11)。根据 C++ 11 标准的推荐,用 unordered_map 代替 hash_map

Prologue

先来回顾一下数据结构中哈希表相关的知识。

哈希表是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数。

哈希表的一个重要问题就是如何解决映射冲突的问题。常用的有两种:开放地址法链地址法

与 map 的区别

STL中,map 对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树,里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map 对应 哈希表,哈希表的特点就是查找效率高,时间复杂度为常数级别 O(1), 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况,使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话,则可以用 map 容器。

基本使用

unordered_map 的用法和 map 大同小异,一个简单示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <unordered_map>
#include <string>
int main(int argc, char **argv) {
std::unordered_map<int, std::string> map;
map.insert(std::make_pair(1, "Scala"));
map.insert(std::make_pair(2, "Haskell"));
map.insert(std::make_pair(3, "C++"));
map.insert(std::make_pair(6, "Java"));
map.insert(std::make_pair(14, "Erlang"));
std::unordered_map<int, std::string>::iterator it;
if ((it = map.find(6)) != map.end()) {
std::cout << it->second << std::endl;
}
return 0;
}

使用自定义类

要使用哈希表,必须要有对应的计算散列值的算法以及判断两个值(或对象)是否相等的方法。
在 Java 中,Object 类里有两个重要方法:hashCodeequals 方法。其中 hashCode 方法便是为散列存储结构服务的,用来计算散列值;而 equals 方法则是用来判断两对象是否等价。由于所有的类都继承自 java.lang.Object 类,因此所有类相当于都拥有了这两个方法。

而在 C++ 中没有自动声明这类函数,STL 只为 C++ 常用类提供了散列函数,因此如果想在 unordered_map 中使用自定义的类,则必须为此类提供一个哈希函数和一个判断对象是否相等的函数(e.g. 重载 == 运算符)。下面是一个简单示例(扒自数据结构上机作业的部分代码):

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::unordered_map;
class Person {
public:
string phone;
string name;
string address;
explicit Person() {}
explicit Person(string name, string phone, string address): name(name), phone(phone), address(address) {}
// overload operator==
bool operator==(const Person& p) {
return this->phone == p.phone && this->name == p.name
&& this->address == p.address;
}
inline friend std::ostream& operator<<(std::ostream& os, Person& p) {
os << "[Person] -> (" << p.name << ", " << p.phone << ", "
<< p.address << ")";
return os;
}
};
// declare hash<Person>
namespace std {
template <>
struct hash<Person> {
std::size_t operator()(const Person& p) 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>()(p.phone)
^ (hash<string>()(p.name) << 1)) >> 1)
^ (hash<string>()(p.address) << 1);
}
};
}
unordered_map<string, Person> phoneMap;
void selectByPhone() {
string phone;
cout << "Input the phone number: "; cin >> phone;
unordered_map<string, Person>::iterator it;
int size = phoneMap.size();
for(int pc = 0; pc < size; pc++) {
if((it = phoneMap.find(phone)) != phoneMap.end()) {
cout << "Query result: " << it->second << endl;
return;
}
}
cout << "Query result : target_not_found" << endl;
}

关于哈希值如何计算,前面我写过一篇文章专门介绍这个:hashCode 方法及 equals 方法的规范

文章目录
  1. 1. Prologue
  2. 2. 与 map 的区别
  3. 3. 基本使用
  4. 4. 使用自定义类