一、前言

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?i2) 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_setstd::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_mapstd::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_multisetstd::unordered_multiset<int> umset;// 插入元素umset.insert(10);umset.insert(20);umset.insert(20);  // 重復元素 20umset.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_multimapstd::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）相比，無序容器具有更快的平均性能，但缺乏排序功能，因此適用場景有所不同。無序容器更適合那些不依賴元素順序、但需要快速查找、插入和刪除操作的應用，而關聯式容器則適合需要元素有序、能夠按順序遍歷的情況。

總體來說，選擇合適的容器應根據具體的需求，權衡性能、內存使用、元素順序等因素。在許多情況下，無序容器提供了一種更加高效的解決方案。