unordered_map的使用
简介
无序映射(Unordered maps)是用于存储键值和映射值组合成的元素的关联容器,并允许基于其键快速检索各个元素。在unordered_map中,键值通常用于唯一地标识元素,而映射值是具有与该键关联的内容的对象。键的类型和映射的值可能会有所不同。
一、unordered_map内部实现
unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。
二、与map的区别
1.map
1,map内置红黑树,使得查找,插入,删除的平均时间复杂度为O(logN)。
2,map内部元素有序
2.unordered_map
1,unordered_map查找,插入,删除的平均时间复杂度为 O(1)。
2,unordered_map内部元素无序
三、问题
当我们的输入数据随机时,每个项平均只会遇到O(1)的冲突,但是如果我们输入特殊数据使得这些输入都产生冲突,就会变成O(n^2)。文章来源:https://www.toymoban.com/news/detail-662628.html
四,解决方案
参考文章:https://codeforces.com/blog/entry/62393%E3%80%82文章来源地址https://www.toymoban.com/news/detail-662628.html
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<int,int,custom_hash>mp;
到了这里,关于unordered_map的使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!