在 C++ 中使用 HashMap

在 C++ 中，雜湊映射由 std::unordered_map 提供；std::map 則是相關的鍵值容器，會依序排列鍵。兩者都是關聯式容器：每個鍵都唯一，並對應一個映射值。不同的鍵可以對應相同的值。如果需要依鍵查找，可以使用任一容器；選擇時應考量是否需要依序走訪。

C++ 標準並未指定 std::map 必須採用哪種內部實作。其可觀察到的順序取決於鍵的比較方式；使用預設比較器時，鍵會依遞增順序排列。相較之下，std::unordered_map 使用雜湊函式與桶，走訪順序未指定。不要依賴某次執行中剛好看到的順序。

C++ 中的雜湊映射如何運作

引入 <map> 或 <unordered_map>，並宣告鍵與映射值的型別，例如 std::map<int, std::string>。insert 只會在鍵不存在時加入鍵值組；透過 operator[] 指派時，若鍵尚不存在，就會先插入值初始化的映射值，再對它指派。對 int 這類純量映射型別而言，值初始化會先產生零，再進行指派。若鍵已存在，指派會更新其值，不會建立重複的鍵。若要先確認鍵是否存在再使用其值，請使用 find。at 也能查找鍵，但找不到鍵時會回報 std::out_of_range。

提供的執行紀錄顯示，原始的兩個範例都成功執行。下方的 std::map 輸出是紀錄中的輸出；後面的無序容器範例新增了走訪迴圈，因此不對修改後的範例聲稱任何特定輸出順序。

使用 std::map 管理有序鍵

當鍵需要依比較器順序走訪，或需要有序操作（例如尋找大於或等於某個值的第一個鍵）時，請使用 std::map。搜尋、插入與移除操作的時間複雜度為對數時間 O(log n)，其中 n 是元素數量。這種可預期的成本與有序走訪，適合用於報表、範圍查詢及排序後的清單。標準保證的是排序行為，並未指定必須使用特定的樹狀結構實作。

執行此範例：

本節中的程式碼以及顯示的標籤或輸出仍為英文。

#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> players;
  players.emplace(2, "Lin Dan");
  players.emplace(1, "Chen Long");

  const auto found = players.find(1);
  if (found != players.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : players) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

1: Chen Long
1: Chen Long
2: Lin Dan

查找結果會輸出鍵 1；迴圈會依比較器順序走訪各鍵，因此無論插入順序為何，1 都會排在 2 前面。

使用 std::unordered_map 進行雜湊查找

當依鍵查找是首要需求，而不需要排序後的走訪結果時，請選擇 std::unordered_map。搜尋、插入與移除操作平均為 O(1)，但在最壞情況下可能需要 O(n)，包括許多鍵發生雜湊碰撞時。重新雜湊也可能改變走訪順序並使迭代器失效。此容器有自身的雜湊與相等性要求：相等的鍵必須產生相同的雜湊值。

執行此範例：程式碼仍以英文輸出 Players: 這個標籤；程式碼區塊依要求原樣保留。

本節中的程式碼以及顯示的標籤或輸出仍為英文。

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, int> scores;
  scores["Ada"] = 8;
  scores["Lin"] = 11;

  const auto found = scores.find("Ada");
  if (found != scores.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : scores) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
  std::cout << "Players: " << scores.size() << '\n';
}

範圍式迴圈會走訪 scores 中的每個項目。項目可能以任意順序出現，C++ 標準與此範例都不保證特定順序。如果呈現時需要排序，請另外整理鍵的清單並排序。

如何在 std::map 與 std::unordered_map 之間選擇

若要統計單字頻率，或建立不在意順序的快取，std::unordered_map 通常是自然的選擇。需要排序輸出或依鍵進行範圍查詢時，請使用 std::map。如果無序容器符合查找需求，但呈現時仍要排序，請先收集鍵並排序，再輸出；不要假設容器的走訪順序。選擇容器時，除了平均速度，也要考量所需行為；若效能對應用程式很重要，請使用具代表性的資料進行基準測試。

兩種容器都支援鍵值存取，但走訪與效能保證不同。若走訪時必須依鍵排序，請使用 std::map；若需要雜湊查找且不在意順序，請使用 std::unordered_map。如需另一個有序走訪範例，請參閱 C++ 中的中序走訪。