10、STL中的unordered_map使用方法

一、了解

1、unordered_map(哈希)

unordered_map是借用哈希表实现的关联容器。

• 访问键值对O（1），最坏情况O（n），例如哈希冲突严重时。【n是一个哈希桶的元素数量】

• unordered_map特性

  • 键值对存储：（key-value）每一个键对应一个值
  • 无序：元素顺序取决于哈希函数和元素添加顺序。
  • 哈希表表现：哈希表实现。键用哈希函数生成对应的索引。
  • 自定义哈希函数和相等函数：可以自己定义函数。

• unordered_map 性能

  • 哈希冲突解决方法：链表或其他数据结构解决冲突。

  • 如下图：
    
    

  • 负载因子和重哈希：

    • 负载因子：已存储元素数量 / 桶的总数量。。【一般为 1 】触发哈希表扩容（rehash）。
    • 重哈希：当加载因子超过要求，就要重新分配元素并增加哈希桶数量。以保持高效性。

  • 内存开销：哈希表需要额外内存管理桶，可能比红黑树占用更多总内存。

• 常见问题：

• 1、如何处理unordered_map中的哈希冲突？

  • unordered_map处理哈希冲突的一种常见方法是链地址法，即在冲突发生时，所有具有相同哈希值的元素会被存储在同一个哈希桶的链表中。当查找一个键时，首先会使用哈希函数计算其哈希值，定位到对应的桶，然后通过遍历链表来查找具有相应键的元素。

• 2、unordered_map的性能瓶颈在哪里？

  • 重哈希操作成本很高。如果使用的负载因子超出要求。发生重哈希，就容易出现瓶颈。

• 3、如何优化性能瓶颈？

  • 可以自定义哈希函数，使用质量更好的哈希函数，减少哈希冲突。负载因子低了会导致内存消耗大，负载因子打了就容易冲突。所以，当知道需要存储的元素时，提前使用reserve预分配空间，减少重哈希。

• 使用的头文件

#include <unordered_map>

二、初始化

unordered_map<KeyType, ValueType> myMap;
键类型 KeyType：必须支持 < 运算符，或传入自定义比较函数。
值类型 ValueType：任意类型（包括自定义类型）。

int main(){pair<int,int>pair1={1,2};pair<int,int>pair2=make_pair(1,2);unordered_map<int ,int>unorderedmap1={{1,2},{1,2}};unordered_map<int ,int>unorderedmap2={pair1,pair2};unordered_map<int ,int>unorderedmap3(unorderedmap2);unordered_map<int ,int>unorderedmap4=unorderedmap3;unordered_map<int ,int>unorderedmap5{pair<int,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 hash<string>()(p.name) ^ hash<int>()(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_map<Person, int, PersonHash, PersonEqual> customMap;

四、常用函数

1、总结

2、例子

• 首先是这里用的头文件

#include <iostream>
#include<unordered_map>
#include <utility>
using namespace std;

2.1、插入操作

• insert({key-value})
  • 插入键值

int main(){unordered_map<int,int>m;m.insert({1,2});for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//1 2}
}

• insert(pair)
  • 插入pair

int main(){pair<int,int>p={1,2};unordered_map<int,int>m;m.insert(p);for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//1 2}
}

• insert(other_unordered_map_first，other_unordered_map_end)
  • 插入另一个哈希map

int main(){unordered_map<int,int>m;unordered_map<int,int>tmp{{2,3},{2,3}};m.insert(tmp.begin(),tmp.end());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3}
}

• inserrt(pos , {key-value})
  • 在pos插入键值

int main(){unordered_map<int,int>m={{1,2}};m.insert(m.begin(),{3,4});for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//3 4//1 2}
}

2.2、删除操作

• erase(first , end)
  • 删除当前这个map 在这个范围内的键值对

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};m.erase(m.begin(),++m.begin());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3//1 2}
}

• erase(pos)
  • 删除pos的键值对

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};m.erase(m.begin());for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//2 3//1 2}
}

2.3、访问操作

• [key]运算符
  • 查key对应的值

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m[1]<<endl;//2}

• at(key)
• 查key对应的值

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.at(1)<<endl;//2}

• begin()
  • 返回第一个

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.begin()->first<<endl;//3cout<<m.begin()->second<<endl;//4
}

• end()
  • 返回最后一个

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};cout<<m.end()->first<<endl;//cout<<m.end()->second<<endl;//
}

2.4、查询操作

• find(key)
  • 找key键值的位置

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};auto i =m.find(1);cout<<i->first<<endl; //1cout<<i->second<<endl;//2
}

• count(key)
  • 找key的键值数量

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};auto i =m.count(1);cout<<i<<endl; //1}

2.5、容量操作

• size()
  • 查找map的数量

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};int num = m.size();cout<<num<<endl; //3}

• empty
  • 当前map是否为空

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};if(m.empty()==1){cout<<"m是空的"<<endl;}else{cout<<"m不是空的"<<endl;}//m不是空的}

2.6、交换操作

• swap(other_unordered_map)
  • 交换2个map

int main(){unordered_map<int,int>m={{1,2},{2,3},{3,4}};unordered_map<int,int>s={{3,4}};m.swap(s);for(auto i:m){cout<<i.first<<" "<<i.second<<" "<<endl;//3 4}
}