unordered_map 是一种哈希表数据结构,通过哈希函数将键值对映射到索引。它支持快速插入(o(1) 平均时间复杂度)、查找和访问,并且占用空间小。然而,哈希函数可能会导致碰撞,并且元素的存储顺序是无序的。
unordered_map 用法详细讲解
什么是 unordered_map?
unordered_map 是一种哈希表数据结构,用于存储键值对。与 map 类似,但它通过哈希函数将键映射到索引,而不是使用平衡树。
如何使用 unordered_map?
-
创建 unordered_map:
unordered_map<int string> myMap;</int>
-
插入元素:
myMap[1] = "One";
-
访问元素:
cout
-
查找元素:
if (myMap.find(2) != myMap.end()) { cout
-
删除元素:
myMap.erase(1);
优点:
- 快速插入和查找:哈希表实现提供了 O(1) 的平均时间复杂度。
- 占用空间小:与平衡树相比,哈希表通常占用更少的空间。
- 简单易用:unordered_map 通过键直接访问值,使用非常方便。
缺点:
- 潜在碰撞:哈希函数可能会导致碰撞,即不同的键映射到相同的索引。
- 无序性质:哈希表中的元素不是按顺序存储的。
注意事项:
- 确保提供一个好的哈希函数以最大限度地减少碰撞。
- 对于需要有序存储的情况,应使用 map。
- unordered_map 存储键的类型必须可哈希,如 int、string 等。