STL 容器深度剖析：hash_map 實現原理與效能權衡

為何選擇 hash_map？

專案中大量證券交易資料查詢，初期使用 std::map（紅黑樹，查詢 O(log n)）。同事建議改用 hash_map（雜湊表，查詢接近 O(1)）。經評估，資料量達萬筆以上時，hash_map 查詢速度顯著優於 map，雖記憶體佔用較大，但在現代伺服器環境下可接受。

hash_map 核心機制

1. 雜湊函數：將 Key 映射為 size_t 雜湊值。
2. 桶陣列：分配大型指標陣列，每個桶為指向節點鏈表的頭指標。
3. 索引計算：bucket_index = hash_value % bucket_count。
4. 衝突解決：同一桶內以鏈表（或開放定址法）串聯，查詢時逐節點比較 key_equal。

理想情況每桶 0~1 節點，查詢僅需 1 次雜湊計算 + 0~1 次比較。

跨平台標頭檔處理

#if defined(__GNUC__)
  #if __GNUC__ < 3 && __GNUC__ >= 2 && __GNUC_MINOR__ >= 95
    #include <hash_map>
  #elif __GNUC__ >= 3
    #include <ext/hash_map>
    using namespace __gnu_cxx;
  #else
    #include <hash_map.h>
  #endif
#elif defined(_MSC_VER)
  #if _MSC_VER >= 1300  // VS.NET 2003+
    #include <hash_map>
    using namespace stdext;
  #else
    #error "std::hash_map not available"
  #endif
#elif defined(__sgi__)
  #include <hash_map>
#else
  #error "std::hash_map not available"
#endif

自訂雜湊與比較函數範例

#include <string>
#include <iostream>

struct str_hash {
    size_t operator()(const std::string& s) const {
        return __stl_hash_string(s.c_str());  // SGI 內建字串雜湊
    }
};

struct str_equal {
    bool operator()(const std::string& a, const std::string& b) const {
        return a == b;
    }
};

int main() {
    hash_map<std::string, std::string, str_hash, str_equal> mp;
    mp.insert({ "hcq", "20" });
    mp["sgx"] = "24";
    mp["sb"] = "23";

    std::cout << mp["sb"] << std::endl;  // 23
    if (mp.find("hcq") != mp.end())
        std::cout << mp["hcq"] << std::endl;  // 20
    return 0;
}

hash_map vs map 關鍵差異

選型決策指南

綜合考量三因素：

• 查詢頻率極高、資料量大、不需有序遍歷 → hash_map（或 C++11 unordered_map）。
• 記憶體極度受限、資料量中小、需有序輸出 → map。
• 資料量小（<1000） → 差異可忽略，優先用 map 簡化代碼。

避坑指南

1. 自訂型別作 Key 必須提供 Hash 與 Equal，且兩者邏輯一致（a==b ⇒ hash(a)==hash(b)）。
2. 避免在迴圈中頻繁 operator[] 查詢不存在的鍵，會導致大量預設構造與擴容；改用 find()。
3. 預估資料量時可呼叫 reserve(n)（或 rehash）減少重雜湊次數。
4. 多執行緒環境下 hash_map 非執行緒安全，需自行加鎖或改用 TBB/folly 等並發雜湊表。

總結

hash_map 以空間換時間，針對高頻查詢場景提供近乎常數時間的存取。理解其雜湊函數、桶機制、衝突處理與擴容策略，有助於在效能與資源之間做出正確工程決策。現代 C++ 建議直接使用標準化的 std::unordered_map，介面一致且支援自訂分配器。