在 C++ 中使用 HashMap
HashMap 是一種重要的資料結構,包含鍵值對,其中可以使用相關鍵檢索值。每個鍵都對映到 HashMap 中的一個特定值。
在迭代期間使用鍵,我們可以更快地訪問相應的值。因此,在檢索值時,HashMap 被認為是一種有效且必不可少的資料結構,具有任何型別的鍵和值。
在 C++ 11 之前,標準定義的雜湊表不存在於 C++ 的標準庫中,但有些不同的實現者有雜湊表的非標準變體,通常稱為 HashMap。與 C++ 11 一起,雜湊表的標準實現被新增到標準庫中。
儘管如此,由於雜湊表的各種變體是來自不同庫的 HashMap,因此決定使用單獨的名稱來呼叫新實現以避免混淆。
因此,在 C++ 中,std::unordered_map
是 HashMap 的替代名稱,但另一個對映使用鍵值對概念,std::map
。
std::unordered_map
和 std::map
之間存在關鍵區別。顧名思義,std::unordered_map
中的元素是無序的,而 std::map
中的元素是有序的。
在 C++ 中使用帶有 std::map
的 HashMap
std::map
屬於關聯容器的類別,其中元素儲存在對映的鍵值對中。在 std::map
和 std::unordered_map
中,鍵應該始終是唯一的,但可以有多個對映值相似的唯一鍵。
std::map
是使用自平衡二叉搜尋樹(AVL 樹/紅黑樹)實現的。BST(Self-Balancing Binary Search Tree)的主要特點是當插入和刪除元素時高度總是自動保持在最小值。
在 std::map
中,平均時間複雜度以對數方式取決於儲存的元素數量;因此,一個操作發生平均需要 O(log n)
時間。在 O(log n)
中,O
是指 Big O
表示法,n
是指儲存的元素數。
因此,BST 在建立和維護有序列表時很有幫助。
例子:
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> Players;
Players.insert(std::pair<int, string>(2, "Lin Dan"));
Players.insert(std::pair<int, string>(1, "Chen Long"));
cout << "Number of Players " << Players.size() << endl;
for (map<int, string>::iterator it = Players.begin(); it != Players.end(); ++it) {
cout << (*it).first << ": " << (*it).second << endl;
}
}
輸出:
Number of Players 2
1: Chen Long
2: Lin Dan
在 C++ 中使用帶有 std::unordered_map
的 HashMap
std::unordered_map
是使用 C++ 中的雜湊表實現的。雜湊表也屬於關聯容器。對映的值儲存在桶或槽陣列中的雜湊表中,可以從中檢索必要的值。
這個索引是使用雜湊函式,雜湊碼完成的。std::unordered_map
的搜尋、插入和刪除的平均時間複雜度是 O(1)
,其中 O
是 Big O
表示法,這就是 std::unordered_map
非常有效。
例子:
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, int> info;
info["Age"] = 18;
info["Year"] = 2022;
info["Number of Players"] = 15;
for (auto x : info)
cout << x.first << " " << x.second << endl;
}
輸出:
Number of Players 15
Year 2022
Age 18
C++ 中的關鍵差異以及何時使用每個對映
當比較 std::unordered_map
和 std::map
時,兩者之間的效率差距是巨大的。
std::unordered_map | 標準::地圖 | |
---|---|---|
搜尋時間 | O(log n) | O(1) |
插入時間 | O(log n) + 再平衡時間 | O(1) |
刪除時間 | O(log n) + 再平衡時間 | O(1) |
std::unordered_map
顯然比 std::map
有相當大的效能優勢。這主要是因為 std::unordered_map
可以直接定址值,因為它們被放置在插槽中,因此沒有需要保留的順序。
另一方面,std::map
有一個需要保留的順序;因此,它會消耗更多時間。對於小型資料集,這種效率可能不可見,但對於大型資料集,這種差異是巨大的。
std::unordered_map
可用於從資料集中訪問單個元素或在不需要順序時保持元素計數。
std::map
也確實比 std::unordered_map
有一些優勢。通常,BST 可以比雜湊表更快地實現,我們可以用我們喜歡的方式來實現,但是對於雜湊,我們需要嚴重依賴庫。
因此,與 std::unordered_map
相比,std::map
可以輕鬆實現。此外,在排序方面,在 std::map
中對鍵進行排序比在 std::unordered_map
中排序要容易得多,因為 inorder traversing 不是雜湊表的自然操作,而是適用於 BST。
std::map
可用於按排序順序列印資料等情況,其中需要對資料進行排序以進行搜尋查詢、排序統計等。
std::map
和 std::unordered_map
都有某些相似之處和不同之處,可以根據當時的需要進行操作。
Nimesha is a Full-stack Software Engineer for more than five years, he loves technology, as technology has the power to solve our many problems within just a minute. He have been contributing to various projects over the last 5+ years and working with almost all the so-called 03 tiers(DB, M-Tier, and Client). Recently, he has started working with DevOps technologies such as Azure administration, Kubernetes, Terraform automation, and Bash scripting as well.