哈希表是一种数据结构,它可以快速地存储和查找键值对。哈希表的核心思想是通过一个哈希函数,将键映射到一个数组的某个位置,然后在该位置存储或查找对应的值。哈希表的优点是查找的时间复杂度是O(1),缺点是可能会发生哈希冲突,即不同的键被映射到同一个位置,需要额外的方法来解决。
在C++中,可以使用STL中提供的unordered_map来实现哈希表。unordered_map是一个模板类,它接受两个类型参数,分别表示键和值的类型。例如:
// 创建一个以int为键,以string为值的哈希表
unordered_map<int, string> umap;
unordered_map提供了一些常用的成员函数和操作符来操作哈希表,例如:
- umap[key] = value; 通过下标运算符插入或修改一个键值对。
- umap.insert({key, value}); 通过insert函数插入一个键值对。
- umap.erase(key); 通过erase函数删除一个键值对。
- umap.find(key); 通过find函数查找一个键是否存在,返回一个迭代器指向该位置或者end()表示不存在。
- umap.count(key); 通过count函数统计一个键出现的次数,返回0或1。
- umap.size(); 通过size函数返回哈希表中元素的个数。
- umap.empty(); 通过empty函数判断哈希表是否为空。
- umap.clear(); 通过clear函数清空哈希表中所有元素。