编辑“︁C++unordered multimap”︁

{{Note|本条目是[[C++STL容器]]系列的一部分，介绍无序关联容器`unordered_multimap`的特性与用法。}}

== 概述 ==
'''unordered_multimap'''是C++标准模板库(STL)中的无序关联容器，允许存储键值对（key-value pairs）且'''允许重复键'''。与`unordered_map`不同，其不要求键的唯一性，采用哈希表实现，提供平均O(1)时间复杂度的插入、删除和查找操作。

=== 核心特性 ===
* '''无序性'''：元素顺序由哈希函数决定，非按键排序。
* '''重复键支持'''：多个元素可拥有相同键。
* '''哈希依赖'''：性能直接受哈希函数质量影响。

== 基本操作 ==
=== 头文件与声明 ===
<syntaxhighlight lang="cpp">
#include <unordered_map>
std::unordered_multimap<KeyType, ValueType> myMap;
</syntaxhighlight>

=== 插入元素 ===
使用`insert()`或`emplace()`：
<syntaxhighlight lang="cpp">
std::unordered_multimap<std::string, int> scores;
scores.insert({"Alice", 90});
scores.emplace("Bob", 85);
scores.insert({"Alice", 95}); // 允许重复键
</syntaxhighlight>

=== 访问元素 ===
需使用迭代器或范围查找（因直接通过键访问可能不唯一）：
<syntaxhighlight lang="cpp">
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << ": " << it->second << '\n';
}
</syntaxhighlight>
'''输出'''：
<pre>
Alice: 90
Alice: 95
</pre>

=== 删除元素 ===
通过迭代器或键删除：
<syntaxhighlight lang="cpp">
scores.erase("Bob"); // 删除所有键为"Bob"的元素
</syntaxhighlight>

== 实际案例 ==
=== 场景：学生成绩管理 ===
存储学生多次考试成绩，允许同名学生（如重名情况）：
<syntaxhighlight lang="cpp">
std::unordered_multimap<std::string, int> gradebook;
gradebook.insert({"Zhang San", 88});
gradebook.insert({"Li Si", 92});
gradebook.insert({"Zhang San", 76}); // 同名不同人

// 查询所有"Zhang San"的成绩
auto zhangs = gradebook.equal_range("Zhang San");
for (auto it = zhangs.first; it != zhangs.second; ++it) {
    std::cout << "Student: " << it->first << ", Score: " << it->second << '\n';
}
</syntaxhighlight>
'''输出'''：
<pre>
Student: Zhang San, Score: 88
Student: Zhang San, Score: 76
</pre>

== 进阶特性 ==
=== 自定义哈希函数 ===
需定义哈希结构体并重载`operator()`：
<syntaxhighlight lang="cpp">
struct MyHash {
    size_t operator()(const std::string& key) const {
        return key.length(); // 简单示例：按字符串长度哈希
    }
};
std::unordered_multimap<std::string, int, MyHash> customMap;
</syntaxhighlight>

=== 负载因子与重组 ===
* '''负载因子''' = 元素数 / 桶数，通过`max_load_factor()`调整。
* 强制重组：`rehash(n)`设置桶数为`n`。

== 性能分析 ==
<mermaid>
graph LR
    A[操作] -->|平均时间复杂度| B[O(1)]
    A -->|最坏情况| C[O(n)]
    D[影响因素] --> E[哈希函数质量]
    D --> F[负载因子]
</mermaid>

== 与相似容器对比 ==
{| class="wikitable"
! 特性 !! unordered_multimap !! unordered_map !! multimap
|-
| 键唯一性 || 否 || 是 || 否
|-
| 排序方式 || 无序 || 无序 || 有序（红黑树）
|-
| 查找复杂度 || O(1) || O(1) || O(log n)
|}

== 数学基础 ==
哈希表性能依赖于：
* 均匀哈希假设：键映射到桶的概率服从均匀分布，即<math>P(h(k) = i) = \frac{1}{m}</math>（m为桶数）。
* 期望链长：<math>E[\text{链长}] = \frac{n}{m}</math>（n为元素数）。

{{Warning|高负载因子可能导致哈希冲突激增，建议保持`max_load_factor()`在0.7~1.0之间。}}

== 总结 ==
`unordered_multimap`适用于需要快速访问且允许键重复的场景，其性能优于有序容器（如`multimap`）但牺牲了顺序性。开发者需权衡需求选择合适容器。

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]