【C++11】哈希表与无序容器：从概念到应用

一、前言

C++11 标准引入了一个非常重要的容器系列——无序容器（unordered containers），包括 unordered_set、unordered_map、unordered_multiset 和 unordered_multimap。这些容器与之前的关联式容器（如 set、map、multiset 和 multimap）类似，但有一个重要区别：无序容器的元素不会按某种顺序（如升序或降序）排列，而是通过哈希表来组织。 因此，访问、插入和删除操作的时间复杂度大大降低（平均情况下为常数时间 O(1)），在许多应用场景下提供了更高效的性能。

下面我们会详细介绍这几种无序容器，以及与对应的关联式容器的区别：

二、哈希表（Hash Table）

首先对于这几个无需容器，其底层都是由哈希表实现的，所以先简单介绍一下哈希表：

哈希表是一种高效的数据结构，它通过哈希函数将键（key）映射到表中一个位置来访问记录，以实现快速的插入、删除和查找操作。

1. 基本概念

核心组成

1. 键（Key）：用于查找的标识符
2. 值（Value）：与键关联的数据
3. 哈希函数（Hash Function）：将键转换为数组索引的函数
4. 数组（桶数组）：存储数据的底层结构
5. 冲突解决机制：处理多个键映射到同一索引的情况

工作原理

1. 当插入键值对时，使用哈希函数计算键的哈希值
2. 将哈希值转换为数组索引（通常通过取模运算）
3. 在该索引位置存储值（或包含键值对的节点）

2. 哈希函数

好的哈希函数应具备以下特性：

• 确定性：相同键总是产生相同哈希值
• 均匀分布：键应均匀分布在哈希表中
• 高效计算：计算速度快

常见哈希函数：

• 除留余数法：h(k) = k mod m
• 乘法哈希：h(k) = floor(m * (k*A mod 1))，其中0 < A < 1
• 针对字符串的哈希函数（如DJB2、FNV等）

3. 冲突解决方法

链地址法（Separate Chaining）

• 每个桶是一个链表（或其他数据结构）
• 冲突元素添加到链表末尾
• 查找时需要遍历链表

开放寻址法（Open Addressing）

• 所有元素都存放在数组本身中
• 当冲突发生时，按照某种探测序列寻找下一个空槽
• 常见探测方法：
  • 线性探测：h(k, i) = (h'(k) + i) mod m
  • 二次探测：h(k, i) = (h'(k) + c₁i + c₂i²) mod m
  • 双重哈希：h(k, i) = (h₁(k) + i*h₂(k)) mod m

4. 性能分析

• 平均情况：
  • 插入、删除、查找：O(1)
• 最坏情况：
  • 所有键映射到同一槽：O(n)

性能取决于：

1. 哈希函数的质量
2. 冲突解决方法
3. 负载因子（load factor）：元素数量/表大小

5. 动态扩容

当负载因子超过阈值（通常0.7-0.8）时：

1. 创建更大的新数组（通常是原大小的2倍左右）
2. 重新计算所有元素的哈希值并插入新数组
3. 释放旧数组空间

6. 应用场景

• 字典/关联数组实现
• 数据库索引
• 缓存系统（如Redis）
• 对象唯一性检查
• 频率统计
• 快速查找需求场景

7. 优缺点

优点：

• 平均情况下常数时间的操作
• 灵活的大小（可动态扩容）
• 适合大数据量处理

缺点：

• 最坏情况下性能较差
• 哈希函数设计影响性能
• 不支持有序遍历（除非使用特殊实现）
• 内存使用可能不如某些数据结构紧凑

二. 无序容器的介绍

1. unordered_set

unordered_set 是一个无序集合，类似于 set，但它不保证元素的顺序。它的每个元素都是唯一的，且基于哈希表进行组织和查找。

特点：

• 元素唯一，不允许重复。
• 基于哈希表存储，查找、插入、删除的平均时间复杂度为 O(1)。
• 不保证元素的顺序。

示例代码

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个 unordered_set
    std::unordered_set<int> uset;

    // 插入元素
    uset.insert(10);
    uset.insert(20);
    uset.insert(30);
    uset.insert(20);  // 重复的 20，不会插入

    // 输出所有元素
    for (const int& val : uset) {
        std::cout << val << " ";  // 输出顺序不确定
    }
    std::cout << std::endl;

    // 查找元素
    if (uset.find(20) != uset.end()) {
        std::cout << "Found 20!" << std::endl;
    } else {
        std::cout << "20 not found!" << std::endl;
    }

    // 删除元素
    uset.erase(30);

    // 再次输出
    for (const int& val : uset) {
        std::cout << val << " ";  // 输出顺序不确定
    }
    std::cout << std::endl;

    return 0;
}

输出示例

10 20 30 
Found 20!
10 20 

2. unordered_map

unordered_map 是一个无序的键值对容器，类似于 map，但它不保证元素的顺序。它的键是唯一的，每个键都关联着一个值。

特点

• 键唯一，值可重复。
• 基于哈希表存储，查找、插入、删除的平均时间复杂度为 O(1)。
• 不保证元素的顺序。

示例代码

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个 unordered_map
    std::unordered_map<int, std::string> umap;

    // 插入键值对
    umap[1] = "one";
    umap[2] = "two";
    umap[3] = "three";

    // 查找元素
    std::cout << "Key 2: " << umap[2] << std::endl;

    // 输出所有键值对
    for (const auto& pair : umap) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 删除元素
    umap.erase(1);

    // 输出删除后的结果
    std::cout << "After deleting key 1:" << std::endl;
    for (const auto& pair : umap) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

输出示例

Key 2: two
3 -> three
2 -> two
1 -> one
After deleting key 1:
3 -> three
2 -> two

3. unordered_multiset

unordered_multiset 是一个无序集合，允许元素重复。它与 unordered_set 的区别在于，它允许多个相同的元素。

特点

• 允许重复元素。
• 基于哈希表存储，查找、插入、删除的平均时间复杂度为 O(1)。
• 不保证元素的顺序。

示例代码

#include <iostream>
#include <unordered_multiset>

int main() {
    // 创建一个 unordered_multiset
    std::unordered_multiset<int> umset;

    // 插入元素
    umset.insert(10);
    umset.insert(20);
    umset.insert(20);  // 重复元素 20
    umset.insert(30);

    // 输出所有元素
    for (const int& val : umset) {
        std::cout << val << " ";  // 输出顺序不确定
    }
    std::cout << std::endl;

    // 查找元素
    if (umset.count(20) > 0) {
        std::cout << "Found 20!" << std::endl;
    }

    // 删除元素
    umset.erase(20);  // 删除所有 20

    // 输出删除后的元素
    std::cout << "After erasing 20:" << std::endl;
    for (const int& val : umset) {
        std::cout << val << " ";  // 输出顺序不确定
    }
    std::cout << std::endl;

    return 0;
}

输出示例

10 20 30 20 
Found 20!
After erasing 20:
10 30 

4. unordered_multimap

unordered_multimap 是一个无序的键值对容器，允许多个相同的键，每个键可以有多个值。

特点

• 允许重复的键。
• 基于哈希表存储，查找、插入、删除的平均时间复杂度为 O(1)。
• 不保证元素的顺序。

示例代码

#include <iostream>
#include <unordered_multimap>

int main() {
    // 创建一个 unordered_multimap
    std::unordered_multimap<int, std::string> ummap;

    // 插入键值对
    ummap.insert({1, "one"});
    ummap.insert({2, "two"});
    ummap.insert({2, "second two"});  // 重复键
    ummap.insert({3, "three"});

    // 输出所有键值对
    for (const auto& pair : ummap) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    // 查找某个键的所有值
    std::cout << "Values for key 2:" << std::endl;
    auto range = ummap.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }

    // 删除元素
    ummap.erase(2);  // 删除所有键为 2 的元素

    // 输出删除后的结果
    std::cout << "After deleting key 2:" << std::endl;
    for (const auto& pair : ummap) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

输出示例

1 -> one
2 -> second two
2 -> two
3 -> three
Values for key 2:
second two
two
After deleting key 2:
1 -> one
3 -> three

5. 总结

• unordered_set：无序的集合，元素唯一，查找、插入、删除操作平均时间复杂度为 O(1)。
• unordered_map：无序的键值对容器，键唯一，查找、插入、删除操作平均时间复杂度为 O(1)。
• unordered_multiset：无序的集合，允许重复元素，查找、插入、删除操作平均时间复杂度为 O(1)。
• unordered_multimap：无序的键值对容器，允许重复键，查找、插入、删除操作平均时间复杂度为 O(1)。

无序容器非常适合需要快速查找、插入和删除操作的场景，尤其是在不关心元素顺序的情况下。它们比传统的关联式容器（如 set 和 map）具有更高的性能，尤其是在处理大量数据时。

三. 无序容器与关联式容器的对比

C++ 标准库中早期的关联式容器包括 set、map、multiset 和 multimap，这些容器通常基于平衡二叉树（如红黑树）实现，它们自动按照一定的顺序排列元素。无序容器则基于哈希表实现，元素的顺序并不固定。下面对比这两类容器的关键区别。

1. 存储方式

• 关联式容器（set、map 等）：元素存储在一个平衡二叉搜索树中（如红黑树）。树的结构确保了元素总是按一定的顺序排列。
• 无序容器（unordered_set、unordered_map 等）：元素存储在哈希表中，哈希表使用哈希函数将元素分配到不同的桶（bucket）中，因此元素的存储顺序不固定。

2. 时间复杂度

• 关联式容器：所有基本操作（插入、删除、查找）在最坏情况下的时间复杂度为 O(log n)，因为它们基于平衡二叉树，树的深度是 O(log n)。
• 无序容器：在平均情况下，所有基本操作（插入、删除、查找）的时间复杂度为 O(1)，因为哈希表提供了常数时间的查找、插入和删除。但是在极端情况下（比如大量哈希冲突时），最坏情况下的时间复杂度可能降为 O(n)，这时所有元素可能会存储在同一个桶中，形成链表。

3. 元素顺序

• 关联式容器：元素按照键的顺序排列，通常是升序（也可以通过自定义比较器来改变排序方式）。
• 无序容器：元素的顺序是无关紧要的，哈希表中的元素没有固定顺序。

4. 适用场景

• 关联式容器：适用于需要元素保持顺序的场景，或需要按照某种顺序遍历容器的情况。典型应用包括有序的集合、映射等。
• 无序容器：适用于不关心元素顺序的场景，尤其是需要高效查找、插入和删除的情况。如果性能要求很高，并且顺序无关，unordered_* 容器是更好的选择。

5. 迭代器

• 关联式容器：由于元素有序，迭代器会按照元素的顺序进行遍历。遍历结果是按从小到大的顺序排列。
• 无序容器：由于哈希表中元素的顺序不确定，迭代器遍历容器时，元素的顺序无法预测。

6. 内存使用

• 关联式容器：由于需要维护平衡二叉树，关联式容器的内存使用相对较高。每个元素不仅存储其值，还存储指向父节点、左子节点和右子节点的指针。
• 无序容器：无序容器基于哈希表实现，通常会根据桶的数量来预分配内存。哈希表可能会使用更多的内存来管理冲突的桶，但通常能保持较低的内存使用。

四、总结

C++11 引入的无序容器（unordered_set、unordered_map、unordered_multiset、unordered_multimap）为开发者提供了一种更高效的选择，尤其是在对性能要求高且不关心元素顺序的场景中。这些容器的查找、插入和删除操作通常能在常数时间内完成，大大提高了程序的性能。

与传统的关联式容器（如 set 和 map）相比，无序容器具有更快的平均性能，但缺乏排序功能，因此适用场景有所不同。无序容器更适合那些不依赖元素顺序、但需要快速查找、插入和删除操作的应用，而关联式容器则适合需要元素有序、能够按顺序遍历的情况。

总体来说，选择合适的容器应根据具体的需求，权衡性能、内存使用、元素顺序等因素。在许多情况下，无序容器提供了一种更加高效的解决方案。