gp_hash_table
是一种哈希表的实现,旨在提供高效的查找和插入操作。
gp_hash_table
使用开放寻址法(open addressing)作为碰撞解决方法,即当发生哈希冲突时,它会尝试通过探测空槽来找到下一个可用的位置。这个过程不需要额外的链表或链表节点,因此可以节省内存并减少指针解引用的开销。
gp_hash_table
的优点在于其快速的查询和插入操作。它通过哈希函数将键映射到索引位置,并使用线性探测或二次探测等策略来解决冲突。这使得它在大多数情况下都能以常数时间复杂度(O(1))执行这些操作。
另一个重要的特性是gp_hash_table
支持自定义的哈希函数。用户可以定义自己的哈希函数,以根据具体的键类型生成哈希值。这样可以最大程度地减少哈希冲突,提高哈希表的性能。
gp_hash_table
,速度较快(使用开放寻址法);
cc_hash_table
速度稍慢(使用拉链法), 但均快于 map
和 unordered_map
使用gp_hash_table
需要包含头文件<ext/pb_ds/assoc_container.hpp>
和命名空间__gnu_pbds
。
下面是一个简单的示例代码,展示了如何使用gp_hash_table存储字符串类型的键值对,并进行查找和插入操作:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
int main()
{
gp_hash_table<string, int> my_map; // 定义哈希表
my_map["hello"] = 1; // 插入键值对
my_map["world"] = 2;
cout << my_map["hello"] << endl; // 查询键值对
cout << my_map["world"] << endl;
return 0;
}
orz
unordered_map也可以自定义哈希函数的,有点复杂
这个快多了
去了解了一下,自定义哈希函数的方式和stl一样,也确实比unordered_map快,就是只有gcc可以用,看样子会很受linux端C++开发者欢迎
强