C++：无序关联容器

遇到的问题，都有解决方案，希望我的博客能为您提供一点帮助。

一、无序关联容器概述

无序关联容器（如 unordered_set、unordered_map、unordered_multiset、unordered_multimap）基于 ​哈希表（Hash Table）​ 实现，与有序关联容器（如 set、map）的核心区别在于：

• ​无序性：元素不按特定顺序存储，而是通过哈希函数快速定位。
• ​时间复杂度：平均时间复杂度为 ​O(1)​（理想情况下），最坏情况为 ​O(n)（哈希冲突严重时）。

​1. 哈希表结构

无序关联容器的底层是一个 ​动态数组（桶数组）​，每个桶（Bucket）存储一个链表或另一哈希结构（如红黑树）来处理冲突。

• ​桶数组：初始大小为默认值（如 8），随元素插入动态扩容。
• ​哈希函数：将键（Key）映射为桶索引：

  index = hash(key) % bucket_count();

结构示例： 

Bucket 0: Key1 → Key2 → nullptr
Bucket 1: Key3 → nullptr
Bucket 2: nullptr
...
Bucket N: Key4 → Key5 → nullptr

​2. 冲突解决策略

C++标准库采用 ​链地址法（Separate Chaining）​：

• 每个桶维护一个链表（单链表），哈希冲突时，元素追加到链表尾部。
• 示例：插入键 "apple" 和 "apply"（假设哈希值相同）：

  桶数组索引：3  
  → 链表节点1: "apple" → 链表节点2: "apply"

​3. 负载因子（Load Factor）与扩容

• ​负载因子：load_factor = size() / bucket_count()。
• ​定义：负载因子 = 元素数量 / 桶数量。
• ​默认阈值：1.0（超过时触发扩容）。
• ​扩容触发条件：当 load_factor > max_load_factor（默认 1.0）时，触发 rehash。
• ​扩容机制：
  1. 创建新的桶数组（大小通常为质数，约为原大小的两倍）。
  2. 对所有元素重新计算哈希值，并插入新桶。
  3. 旧桶链表节点被逐个移动到新桶（无需重建元素对象）。

4、无序容器的优势与使用场景

4.​1. 优势

• ​性能优势：哈希表在理想情况下（低冲突）提供常数时间操作，适合高频操作。
• ​简化代码：无需定义关键字的比较运算符（仅需哈希函数和 ==）。

​4.2. 何时选择无序容器？

• 关键字类型无自然顺序（如 UUID、随机生成的数据）。
• 性能测试表明哈希技术能显著提升效率。
• 无需维护元素顺序，且希望减少插入/查找时间。

二、无序容器的操作与示例

​1、支持的操作

无序容器提供与有序容器相同的接口，包括：

• ​插入：insert、emplace
• ​查找：find、count
• ​删除：erase
• ​遍历：迭代器（但顺序不确定）

2、STL中的无序容器接口

2.1. 容器定义

#include <unordered_set>
#include <unordered_map>// 定义示例
std::unordered_set<int> uset;                  // 唯一键集合
std::unordered_map<std::string, int> umap;      // 键值对集合
std::unordered_multiset<int> umset;            // 允许重复键的集合
std::unordered_multimap<std::string, int> ummap; // 允许重复键的键值对集合

2.2. 插入元素

• insert：插入键或键值对，返回是否成功（对unordered_set/map）。

• emplace：直接构造元素，避免拷贝。

• operator[]（仅unordered_map）：若键不存在，插入默认值；存在则返回引用。

示例：

umap.insert({"apple", 5});          // 插入键值对
umap.emplace("banana", 3);         // 直接构造元素
umap["orange"] = 8;                // 使用operator[]插入或修改

2.3. 查找元素

• find：返回指向元素的迭代器，未找到返回end()。

• count：返回键的出现次数（对multi容器有效）。

• equal_range：返回匹配键的范围迭代器对。

示例：

auto it = umap.find("apple");
if (it != umap.end()) {std::cout << "Found: " << it->second << std::endl;
}size_t cnt = ummap.count("apple"); // 统计键出现的次数

2.4. 删除元素

• erase：通过迭代器、键或范围删除元素。

• clear：清空所有元素。

示例：

umap.erase("apple");               // 删除键为"apple"的元素
auto it = umap.find("banana");
if (it != umap.end()) {umap.erase(it);                // 通过迭代器删除
}
umap.clear();                      // 清空容器

2.5. 桶管理接口

• bucket_count()：返回当前桶的数量。

• bucket_size(n)：返回第n个桶中的元素数量。

• bucket(key)：返回键所在的桶索引。

2.5.1. 桶接口

函数	作用
c.bucket_count()	返回当前使用的桶数量（非最大值）。
c.max_bucket_count()	返回容器支持的最大桶数量（受实现或内存限制）。
c.bucket_size(n)	返回第 n 个桶中的元素数量（用于检查桶负载情况）。
c.bucket(k)	返回键 k 所在的桶索引（用于定位元素分布）。

---

2.5.2. 桶迭代

类型/函数	作用
local_iterator	遍历单个桶元素的迭代器（非 const 版本）。
const_local_iterator	遍历单个桶元素的常量迭代器（不可修改元素）。
c.begin(n), c.end(n)	返回第 n 个桶的起始和结束迭代器（用于遍历桶内元素）。
c.cbegin(n), c.cend(n)	返回第 n 个桶的常量起始和结束迭代器。

size_t buckets = umap.bucket_count();
size_t bucket_idx = umap.bucket("apple");
size_t elements_in_bucket = umap.bucket_size(bucket_idx);

2.5.3. 哈希策略

函数/操作	作用
c.load_factor()	返回当前平均每个桶的元素数量（size() / bucket_count()）。
c.max_load_factor()	返回容器试图维持的最大负载因子（默认通常为 1.0）。
c.rehash(n)	重组哈希表，使桶数量至少为 n，并满足 bucket_count > size() / max_load_factor。
c.reserve(n)	预留空间，使容器可保存 n 个元素而无需 rehash（自动调整桶数量）。

关键逻辑：

• 当 load_factor() > max_load_factor() 时，容器自动增加桶数量（触发 rehash）。

• rehash(n) 强制重组哈希表，适用于预知元素数量增长的场景。

• reserve(n) 等价于 rehash(ceil(n / max_load_factor()))，避免频繁重组。

---

三、自定义哈希与比较函数

1. 自定义哈希函数

为自定义类型作为键时，需提供哈希函数。哈希函数需满足：

• 相同输入产生相同哈希值。

• 不同输入尽可能产生不同哈希值（减少冲突）。

示例：

struct Person {std::string name;int age;
};// 自定义哈希函数
struct PersonHash {size_t operator()(const Person& p) const {return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);}
};std::unordered_set<Person, PersonHash> person_set;

2. 自定义相等比较

默认使用operator==，可自定义相等谓词。

struct PersonEqual {bool operator()(const Person& a, const Person& b) const {return a.name == b.name && a.age == b.age;}
};std::unordered_set<Person, PersonHash, PersonEqual> person_set;

3. 使用std::hash组合（C++17）

通过组合多个哈希值，减少冲突概率。

template <typename T>
void hash_combine(size_t& seed, const T& val) {seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}struct PersonHash {size_t operator()(const Person& p) const {size_t seed = 0;hash_combine(seed, p.name);hash_combine(seed, p.age);return seed;}
};

---

四、性能优化

1. 优化策略

• 预分配桶数量：减少重哈希次数。

  std::unordered_map<std::string, int> umap(1000); // 初始1000个桶

• 调整最大负载因子：平衡内存与性能。

  umap.max_load_factor(0.75); // 负载因子超过0.75时触发重哈希

• 预留空间：提前分配足够桶。

  umap.reserve(5000); // 预留至少5000个元素的空间

2. 注意事项

• 哈希函数质量：差的哈希函数导致频繁冲突，性能下降。

• 键的不可变性：插入后修改键可能导致容器状态不一致。

• 迭代器失效：

  • 插入可能触发重哈希，使所有迭代器失效。

  • 删除仅使被删元素的迭代器失效。

---

五、对比有序关联容器

特性	无序关联容器	有序关联容器
底层实现	哈希表	红黑树
时间复杂度	平均O(1)，最坏O(n)	稳定O(log n)
元素顺序	无序	按键升序排列
内存占用	较高（桶数组+链表）	较低（树节点）
自定义排序	仅哈希函数和相等比较	支持自定义比较函数
适用场景	快速查找，不关心顺序	需要有序遍历或范围查询

---

六、实际应用示例

1. 统计单词频率

std::unordered_map<std::string, int> word_count;
std::string word;
while (std::cin >> word) {++word_count[word];
}// 输出结果（无序）
for (const auto& [word, count] : word_count) {std::cout << word << ": " << count << std::endl;
}

2. 实现LRU缓存

template <typename Key, typename Value>
class LRUCache {
private:using List = std::list<std::pair<Key, Value>>;using Map = std::unordered_map<Key, typename List::iterator>;List lru_list;Map cache_map;size_t capacity;public:LRUCache(size_t cap) : capacity(cap) {}Value* get(const Key& key) {auto it = cache_map.find(key);if (it == cache_map.end()) return nullptr;// 移动访问项到链表头部lru_list.splice(lru_list.begin(), lru_list, it->second);return &(it->second->second);}void put(const Key& key, const Value& value) {auto it = cache_map.find(key);if (it != cache_map.end()) {// 更新现有项并移至头部lru_list.erase(it->second);}// 插入新项到头部lru_list.emplace_front(key, value);cache_map[key] = lru_list.begin();// 超出容量则移除尾部if (cache_map.size() > capacity) {cache_map.erase(lru_list.back().first);lru_list.pop_back();}}
};