C++ map && hash_map 底层实现冲突解决和应用选择等

作者：Monodyee | 2024-03-13 02:33:34

踩

参考：

一、区别

1.底层实现不同（存储结构的差异）

map：红黑树

hash_map：散列表

2.构造函数不同

map：只需要比较函数

hash_map：需要hash函数

二、使用

map：

hash_map：

三、选择

主要基于三点：查找速度、数据量和内存情况

map：查找时间复杂度为O（logn）

hash_map：查找时间复杂度为O（1），在数据量大的时候效果明显，但其用空间换时间的做法，要考虑内存情况。

四、冲突解决

map：

hash_map：链地址法最常用，另有开放寻址法（线性探测、二次探测和二次哈希）等。

五、底层原理实现

六、其他

Hash_map的默认哈希函数实际上有多个，是根据传入的类型来选择的，体现了泛型编程。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

C++ map && hash_map 底层实现 冲突解决 和 应用选择等