std::unorderd_map 簡介

1. unorderd_map 簡介

1. unorderd_map 簡介
- 簡介
- 1.1. 實現原理
- 1.2. 函數
- 1.3. 問題集
  - 1.3.1. emplace、emplace_hint、insert 的區別
- 1.4. 參考鏈接

簡介

unordered_map 是 C++ 標準庫中的一個容器，它定義在 <unordered_map> 頭文件里。它借助哈希表來存儲鍵值對，能快速查找、插入和刪除元素
快速查找：平均情況下，查找、插入和刪除操作的時間復雜度為 $O (1)$ 。不過在最壞情況下，例如哈希沖突嚴重時，時間復雜度會達到 $O (n)$ 。
無序存儲：unordered_map 不會按照鍵的順序存儲元素，元素的存儲順序由哈希函數決定。
鍵的唯一性：每個鍵在 unordered_map 中是唯一的。若嘗試插入已存在的鍵，新的值會覆蓋舊的值。

1.1. 實現原理

底層實現主要基于哈希表（Hash Table）

哈希函數

unordered_map 使用哈希函數將鍵轉換為一個無符號整數，這個整數將作為數組的索引。
對于基本數據類型（如 int、string 等），標準庫已經提供了默認的哈希函數。
但對于自定義類型，需要用戶自己定義哈希函數。

例如，對于自定義類型 MyKey，可以這樣定義哈希函數：

#include <functional>struct MyKey {int a;double b;// 重載相等運算符，用于比較鍵是否相等bool operator==(const MyKey& other) const {return a == other.a && b == other.b;}
};// 自定義哈希函數
struct MyKeyHash {std::size_t operator()(const MyKey& k) const {// 使用 std::hash 對不同成員進行哈希，然后組合auto h1 = std::hash<int>{}(k.a);auto h2 = std::hash<double>{}(k.b);return h1 ^ (h2 << 1);}
};

哈希桶（Bucket）

哈希表通常由一個數組構成，數組中的每個元素稱為一個哈希桶。
每個哈希桶可以存儲一個或多個鍵值對，當多個鍵通過哈希函數映射到同一個桶時，就會發生哈希沖突。

處理哈希沖突

哈希沖突是指不同的鍵通過哈希函數映射到了同一個桶。
unordered_map 通常使用鏈地址法（Separate Chaining）來處理哈希沖突。
在鏈地址法中，每個哈希桶實際上是一個鏈表（或其他容器，如紅黑樹），當發生哈希沖突時，新的鍵值對會被添加到對應的鏈表中。

以下是一個簡單的示意圖,哈希表數組:

+--------+--------+--------+
| Bucket0| Bucket1| Bucket2|
+--------+--------+--------+
| Node1  | Node3  | Node4  |
| Node2  |        |        |
+--------+--------+--------+

在這個示意圖中，Bucket0 發生了哈希沖突，有兩個鍵值對（Node1 和 Node2）被映射到了這個桶中，它們通過鏈表連接在一起。

插入操作

向 unordered_map 中插入一個鍵值對時，會執行以下步驟：
使用哈希函數計算鍵的哈希值。
根據哈希值找到對應的哈希桶。
檢查該桶中是否已經存在相同的鍵，如果存在，則更新對應的值；如果不存在，則將新的鍵值對插入到桶中（通常是鏈表的頭部）。

查找操作

當查找一個鍵對應的值時，會執行以下步驟：
使用哈希函數計算鍵的哈希值。
根據哈希值找到對應的哈希桶。
遍歷該桶中的鏈表（或其他容器），查找是否存在與給定鍵相等的鍵。如果找到，則返回對應的值；如果未找到，則返回一個表示未找到的標記（如 end() 迭代器）。

刪除操作

刪除操作與查找操作類似，首先找到對應的哈希桶，然后遍歷桶中的鏈表，找到要刪除的鍵值對并將其從鏈表中移除。

負載因子（Load Factor）和擴容

負載因子是指哈希表中元素的數量與哈希桶數量的比值。
當負載因子超過某個閾值（通常是 1.0）時，為了減少哈希沖突，提高查找效率，unordered_map 會進行擴容操作。
擴容時，會創建一個更大的哈希表數組，然后將原有的鍵值對重新哈希到新的數組中。

總結:unordered_map 通過哈希表實現了快速的鍵值對查找、插入和刪除操作。它使用哈希函數將鍵映射到哈希桶，通過鏈地址法處理哈希沖突，并在負載因子過高時進行擴容。這種實現方式使得 unordered_map 在平均情況下具有 O(1) 的時間復雜度。

1.2. 函數

成員方法
迭代器
- begin 返回指向容器中第一個鍵值對的正向迭代器。
- end 返回指向容器中最后一個鍵值對之后位置的正向迭代器。
- cbegin 和 begin 功能相同，只不過在其基礎上增加了 const 屬性，即該方法返回的迭代器不能用于修改容器內存儲的鍵值對。
- cend 和 end 功能相同，只不過在其基礎上，增加了 const 屬性，即該方法返回的迭代器不能用于修改容器內存儲的鍵值對。
CRUD操作
- operator[key] 該模板類中重載了 [] 運算符，只要給定某個鍵值對的鍵 key，就可以獲取該鍵對應的值。注意，如果當前容器中沒有以 key 為鍵的鍵值對，則其會使用該鍵向當前容器中插入一個新鍵值對。
- at(key) 返回容器中存儲的鍵 key 對應的值，如果 key 不存在，則會拋出 out_of_range 異常。
- find(key) 查找以 key 為鍵的鍵值對，如果找到，則返回一個指向該鍵值對的正向迭代器；反之，則返回一個指向容器中最后一個鍵值對之后位置的迭代器（end 方法返回的迭代器）。
- count(key) 在容器中查找以 key 鍵的鍵值對的個數。
- equal_range(key) 返回一個 pair 對象，其包含 2 個迭代器，用于表明當前容器中鍵為 key 的鍵值對所在的范圍。
- emplace 向容器中添加新鍵值對，直接在容器內部構造元素，避免了不必要的拷貝或移動，效率比 insert 方法高。
- emplace_hint 向容器中添加新鍵值對，接受一個迭代器 position 作為提示參數，用于提高插入效率，但提示錯誤可能會降低效率。
- insert 向容器中添加新鍵值對，通常需要先構造好 value_type 對象，然后將其插入容器，可能會涉及額外的拷貝或移動操作。
- erase 刪除指定鍵值對。可以通過鍵、迭代器位置或迭代器范圍來指定要刪除的元素。
- clear 清空容器，即刪除容器中存儲的所有鍵值對。
屬性
- empty 若容器為空，則返回 true；否則 false。
- size 返回當前容器中存有鍵值對的個數。
- max_size 返回容器所能容納鍵值對的最大個數，不同的操作系統，其返回值亦不相同。
類函數
- swap 交換 2 個 unordered_map 容器存儲的鍵值對，前提是必須保證這 2 個容器的類型完全相等。
底層 hash 相關函數
- bucket_count 返回當前容器底層存儲鍵值對時，使用桶（一個線性鏈表代表一個桶）的數量。
- max_bucket_count 返回當前系統中，unordered_map 容器底層最多可以使用多少桶。
- bucket_size(n) 返回第 n 個桶中存儲鍵值對的數量。
- bucket(key) 返回以 key 為鍵的鍵值對所在桶的編號。
- load_factor 返回 unordered_map 容器中當前的負載因子。負載因子，指的是的當前容器中存儲鍵值對的數量（size）和使用桶數（bucket_count）的比值，即 load_factor = size / bucket_count。
- max_load_factor 返回或者設置當前 unordered_map 容器的負載因子。
- rehash(n) 將當前容器底層使用桶的數量設置為 n。
- reserve 將存儲桶的數量（也就是 bucket_count 方法的返回值）設置為至少容納count個元（不超過最大負載因子）所需的數量，并重新整理容器。
- hash_function 返回當前容器使用的哈希函數對象。

1.3. 問題集

1.3.1. emplace、emplace_hint、insert 的區別

構造方式:
- insert:通常需要先構造好 value_type 對象，然后將其插入容器，可能會涉及額外的拷貝或移動操作。
- emplace 和 emplace_hint:直接在容器內部構造元素，避免了不必要的拷貝或移動，效率更高。
提示參數:
- insert 和 emplace:不需要提示參數。
- emplace_hint:接受一個迭代器作為提示參數，用于提高插入效率，但提示錯誤可能會降低效率。
返回值:
- insert 和 emplace:返回一個 std::pair<iterator, bool>，表示插入是否成功。
- emplace_hint:返回一個指向新插入元素或已存在元素的迭代器。

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> myMap;auto result = myMap.insert({1, "one"});if (result.second) {std::cout << "Inserted successfully." << std::endl;} else {std::cout << "Element already exists." << std::endl;}return 0;
}
int main() {std::unordered_map<int, std::string> myMap;auto result = myMap.emplace(2, "two");if (result.second) {std::cout << "Emplaced successfully." << std::endl;} else {std::cout << "Element already exists." << std::endl;}return 0;
}
int main() {std::unordered_map<int, std::string> myMap;auto hint = myMap.begin();auto it = myMap.emplace_hint(hint, 3, "three");std::cout << "Inserted key: " << it->first << ", value: " << it->second << std::endl;return 0;
}