C++哈希表总结

哈希表总结,C++的哈希表类型以及如何自己实现一个哈希表。

C++中提供的关联数据结构类型#

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

  • 数组
  • set (集合)
  • map(映射)

在C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:

集合 底层实现 是否有序 数值是否可以重复 查询效率 增删效率
std::set 红黑树 有序 O(logn) O(logn)
std::multiset 红黑树 有序 O(logn) O(logn)
std::unordered_set 哈希表 无序 O(1) O(1)

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(logn) O(logn)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的。

unordered_map使用#

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
unordered_map<string, int> age;
// Insert
age["Michael"] = 16;
age.insert({"Chris", 30});
age.insert(std::pair<string, int>{"Bill", 25});

// Search and change
age["Michael"] = 18;
age.at("Chris") = 27;

// Check if key exists
std::string query;
query = "Eric";
if (age.find(query) == age.end())
{
std::cout << query << " is not in the dictionary!" << std::endl;
}

age.erase(query);
if (age.find(query) == age.end())
{
std::cout << query << " is not in the dictionary!" << std::endl;
}
// Iterate
// 也可以用auto替代
for (const std::pair<std::string, int>& tup : age)
{
std::cout << "Name: " << tup.first << std::endl;
std::cout << "Age: " << tup.second << std::endl;
}

其余的map,unordered_set基本上都是同样的用法。

实现hashmap#

  1. begin()function
  2. std::pair,底层使用这个实现
  3. List

Key(int, string)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class myMap
{
private: static const int hashmp = 10;
// use the separate chaining to implement hash table
list<pair<int, string>> table[hashmp];
public:
int size() const {
int s = 0;
for (int i = 0; i < hashmp; ++i)
{
if (table[i].size() != 0)
{ s+=table[i].size(); }
}
return s;
}

int hash(int key)
{
return key % 10;
}
void insert(int key, string value)
{
int h = hash(key);
auto& cell = table[h];
bool keyExists = false;
for (auto bItr = cell.begin(); bItr != cell.end(); ++bItr)
{
if (bItr->first == key)
{
keyExists = true;
cout << "[WARNING] key exits, value "
<< bItr->second << " has changed" << endl;
bItr->second = value;
break;
}
}
if (!keyExists) {
cell.push_back({key, value});
}
return;
}
void dele(int key)
{
int h = hash(key);
auto& cell = table[h];
bool keyExists = false;
for (auto bItr = cell.begin(); bItr != cell.end(); ++bItr)
{
if (bItr->first == key)
{
keyExists = true;
cout << "[WARNING] erase key, the value"
<< bItr->second << " has changed" << endl;
cell.erase(bItr);
break;
}
}
if (!keyExists) {
cout << "[ERROR] The key doesn't exists!" << endl;
}
return;
}

string& operator[](int key)
{
int h = hash(key);
auto& cell = table[h];
for (auto b = cell.begin(); b != cell.end(); ++b)
{
if (b->first == key)
{
return b->second;
}
}

string err = "[ERROR] no key!";
cerr << err << endl;
}

void print()
{
for (int i = 0; i < hashmp; ++i)
{
if (table[i].size() == 0)
{
continue;
}
for (auto b = table[i].begin(); b != table[i].end(); ++b)
{
cout << b->first << ":" << b->second << endl;
}
}
}
};

//test
myMap a;
a.insert(123, "Jack");
a.insert(134, "Bob");
a.insert(432, "Tom");
a.insert(124, "Goe");
cout << "Test:" << endl;
cout << a[123] << endl;
cout << a.size() << endl;
a.insert(124, "Cathy");
a.print();

a.dele(124);
cout << "Test:" << endl;
a.print();