哈希表

发表于 更新于 分类于

哈希表

有的时候，我们需要记录下我们所做的事情，在初学阶段，我们可以使用数组或者容器来进行记录，但是当数据量十分巨大的时候，那么使用哈希表来进行数据的记录会十分方便而且快捷，并且不用担心出现爆栈之类的问题。

在C++中的哈希表实现有三个函数：map,multimap,unordered_map，前面两个函数的实现是利用了红黑树，unordered map的实现是使用了哈希结构直接做映射。

在实际使用中大多数是使用unordered_map，因为使用unordered_map进行查找、删改的效率是最高的。
前面两个函数由于通过在内部实现红黑树的方法来实现哈希表，所以内存占用大，但是在处理一些具有顺序的表的时候更加快速。

unordered_map的使用示例：unordered_map<string,int>mp;//表示键值对由string 映射到 int.
unordered_map函数中常用的成员方法：

at(key)返回容器中储存的键key对应的值，如果key不存在，则会抛出out_of_range异常、find(key)查找以key为键的键值对，如果找到，那么就返回一个指向这个键值对的正向迭代器，反之则返回指向容器中最后一个键值对之后的位置的迭代器（end()） 、count(key)在容器中查找以key作为键的键值对的个数、
emplace() 在容器中添加新键值对，效率比insert()高、

1
2
3
4
5
6
unordered_map<string, int>map;
map["hello"] = 1;
map.emplace("number", 2);
cout << "map[hello] = " << map["hello"] << "map[\"number\"] = " << map["number"] << endl;
out：
map[hello] = 1map["number"] = 2
  • insert() 向容器中添加键值对、
  • erase()删除指定键值对、
  • erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
  • erase(position);删除position处的一个字符(position是个string类型的迭代器)
  • erase(first,last);删除从first到last之间的字符（first和last都是迭代器）
  • clear()清空容器、
  • swap()交换两个unordered_map容器储存的键值对，前提是必须保证这两个容器的类型完全相同。
    记录某一个元素出现的次数：
1
2
3
4
5
6
7
8
9
10
unordered_map<int, int>cnt;
for (int i = 0; i < 3; i++) {
    int q;
    cin >> q;
    cnt[q]++;
}
for (auto q : cnt) {
    cout << q.first<<"\t"<<q.second<< endl;
}
//q.first就是键,q.second就是值。

以下为文心一言的回答：
/**************************************************************************
当然！以下是几个C++中使用哈希表的例子：

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
//例子1：使用unordered_map实现哈希表
#include<iostream>
#include<unordered_map>
int
main(){      
    std::unordered_map<std::string, int> hashTable;  // 添加键值对      
    hashTable["apple"] = 5;      
    hashTable["banana"] = 7;      
    hashTable["orange"] = 3;  // 查找键值对      
    std::cout << "apple: " << hashTable["apple"] << std::endl;  // 遍历哈希表  
    for (constauto& entry : hashTable) {          
        std::cout << entry.first << ": " << entry.second << std::endl;      
}
  return 0;  
}
//例子2：自定义哈希函数
#include<iostream>
#include<unordered_map>// 自定义哈希函数  
structHashFunction {  
std::size_toperator()(const std::pair<std::string, int>& key)const{          
std::size_t hash = 0;  
for (constauto& c : key.first) {              
hash += std::hash<char>()(c);          
}  
return hash ^ (key.second << 1); // 或使用boost::hash_combine (需要包含boost/functional/hash.hpp)      
}  
};  
int
main(){      
std::unordered_map<std::pair<std::string, int>, std::string, HashFunction> hashTable;  
// 添加键值对      
hashTable[{{"apple", 5}}] = "red";      
hashTable[{{"banana", 7}}] = "yellow";      
hashTable[{{"orange", 3}}] = "orange";  
// 查找键值对      
std::cout << hashTable[{{"apple", 5}}] << std::endl;  
// 遍历哈希表  
for (constauto& entry : hashTable) {          
std::cout << entry.first.first << ", " << entry.first.second << ": " << entry.second << std::endl;      
}  
return 0;  
}

这些例子演示了如何使用unordered_map容器来实现哈希表，并在其中存储和访问键值对。第一个例子使用了默认的哈希函数，而第二个例子自定义了哈希函数。这只是C中实现哈希表的简单示例，实际上还有更多的用法和扩展可以探索。请注意，为了运行这些示例，您需要编译器支持C11或更高版本。