在 C++ 中使用 HashMap

1. 在 C++ 中使用帶有 std::map 的 HashMap
2. 在 C++ 中使用帶有 std::unordered_map 的 HashMap
3. C++ 中的關鍵差異以及何時使用每個對映

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 <map>
#include <string>

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 顯然比 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 都有某些相似之處和不同之處，可以根據當時的需要進行操作。