山东省建设部官方网站,网页设计素材主题,谈谈你对网站开发的理解,网站设计开发是啥一、了解
1、unordered_map(哈希)
unordered_map是借用哈希表实现的关联容器。 访问键值对O#xff08;1#xff09;#xff0c;最坏情况O#xff08;n#xff09;#xff0c;例如哈希冲突严重时。【n是一个哈希桶的元素数量】 unordered_map特性 键值对存储#xff…一、了解
1、unordered_map(哈希)
unordered_map是借用哈希表实现的关联容器。 访问键值对O1最坏情况On例如哈希冲突严重时。【n是一个哈希桶的元素数量】 unordered_map特性 键值对存储key-value每一个键对应一个值无序元素顺序取决于哈希函数和元素添加顺序。哈希表表现哈希表实现。键用哈希函数生成对应的索引。自定义哈希函数和相等函数可以自己定义函数。 unordered_map 性能 哈希冲突解决方法链表或其他数据结构解决冲突。 如下图 负载因子和重哈希 负载因子已存储元素数量 / 桶的总数量。。【一般为 1 】触发哈希表扩容rehash。重哈希当加载因子超过要求就要重新分配元素并增加哈希桶数量。以保持高效性。 内存开销哈希表需要额外内存管理桶可能比红黑树占用更多总内存。 常见问题 1、如何处理unordered_map中的哈希冲突 unordered_map处理哈希冲突的一种常见方法是链地址法即在冲突发生时所有具有相同哈希值的元素会被存储在同一个哈希桶的链表中。当查找一个键时首先会使用哈希函数计算其哈希值定位到对应的桶然后通过遍历链表来查找具有相应键的元素。 2、unordered_map的性能瓶颈在哪里 重哈希操作成本很高。如果使用的负载因子超出要求。发生重哈希就容易出现瓶颈。 3、如何优化性能瓶颈 可以自定义哈希函数使用质量更好的哈希函数减少哈希冲突。负载因子低了会导致内存消耗大负载因子打了就容易冲突。所以当知道需要存储的元素时提前使用reserve预分配空间减少重哈希。 使用的头文件
#include unordered_map二、初始化 unordered_mapKeyType, ValueType myMap; 键类型 KeyType必须支持 运算符或传入自定义比较函数。 值类型 ValueType任意类型包括自定义类型。 int main(){pairint,intpair1{1,2};pairint,intpair2make_pair(1,2);unordered_mapint ,intunorderedmap1{{1,2},{1,2}};unordered_mapint ,intunorderedmap2{pair1,pair2};unordered_mapint ,intunorderedmap3(unorderedmap2);unordered_mapint ,intunorderedmap4unorderedmap3;unordered_mapint ,intunorderedmap5{pairint,int(1,2)};
}
三、自定义哈希函数
首先了解负载因子load factor已存储元素数量 / 桶的总数量。 默认当负载因子超过 max_load_factor()通常为 1.0时触发哈希表扩容rehash。 调整桶的数量方法 如下
scores.rehash(50); // 预分配至少容纳 50 个元素的桶
scores.reserve(100); // 预分配至少 100 个元素的容量更友好手动设置哈希函数 , 例如
// 示例自定义类的哈希函数
struct Person {string name;int id;
};// 定义哈希函数
struct PersonHash {size_t operator()(const Person p) const {return hashstring()(p.name) ^ hashint()(p.id);}
};// 定义相等比较
struct PersonEqual {bool operator()(const Person a, const Person b) const {return a.name b.name a.id b.id;}
};// 使用自定义类型的 unordered_map
unordered_mapPerson, int, PersonHash, PersonEqual customMap;
四、常用函数
1、总结 2、例子
首先是这里用的头文件
#include iostream
#includeunordered_map
#include utility
using namespace std;2.1、插入操作
insert({key-value}) 插入键值
int main(){unordered_mapint,intm;m.insert({1,2});for(auto i:m){couti.first i.second endl;//1 2}
}insert(pair) 插入pair
int main(){pairint,intp{1,2};unordered_mapint,intm;m.insert(p);for(auto i:m){couti.first i.second endl;//1 2}
}insert(other_unordered_map_firstother_unordered_map_end) 插入另一个哈希map
int main(){unordered_mapint,intm;unordered_mapint,inttmp{{2,3},{2,3}};m.insert(tmp.begin(),tmp.end());for(auto i:m){couti.first i.second endl;//2 3}
}inserrt(pos , {key-value}) 在pos插入键值
int main(){unordered_mapint,intm{{1,2}};m.insert(m.begin(),{3,4});for(auto i:m){couti.first i.second endl;//3 4//1 2}
}2.2、删除操作
erase(first , end) 删除当前这个map 在这个范围内的键值对
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};m.erase(m.begin(),m.begin());for(auto i:m){couti.first i.second endl;//2 3//1 2}
}erase(pos) 删除pos的键值对
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};m.erase(m.begin());for(auto i:m){couti.first i.second endl;//2 3//1 2}
}2.3、访问操作
[key]运算符 查key对应的值
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};coutm[1]endl;//2}at(key)查key对应的值
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};coutm.at(1)endl;//2}begin() 返回第一个
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};coutm.begin()-firstendl;//3coutm.begin()-secondendl;//4
}
end() 返回最后一个
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};coutm.end()-firstendl;//coutm.end()-secondendl;//
}2.4、查询操作
find(key) 找key键值的位置
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};auto i m.find(1);couti-firstendl; //1couti-secondendl;//2
}count(key) 找key的键值数量
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};auto i m.count(1);coutiendl; //1}2.5、容量操作
size() 查找map的数量
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};int num m.size();coutnumendl; //3}empty 当前map是否为空
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};if(m.empty()1){coutm是空的endl;}else{coutm不是空的endl;}//m不是空的}2.6、交换操作
swap(other_unordered_map) 交换2个map
int main(){unordered_mapint,intm{{1,2},{2,3},{3,4}};unordered_mapint,ints{{3,4}};m.swap(s);for(auto i:m){couti.first i.second endl;//3 4}
}
