C++ STL 中 hash_map 完整指南：哈希函數、比較函數與自定義類型應用

引言

在 C++ STL 中，hash_map 是一個高效的關聯式容器，以鍵值對形式存儲數據，並通過哈希函數實現常數級別的平均查找、插入與刪除操作。不同於 map 的紅黑樹實現，hash_map 依賴哈希表，因此在聲明時除了指定鍵和值的類型外，還需提供哈希函數與鍵值相等比較函數。本文將深入解析 hash_map 的核心組件，並示範如何為自定義類型正確配置這些組件。

一、哈希函數詳解

哈希函數負責將鍵映射為桶索引。SGI STL 為內建類型提供了預設的哈希函數，其本質是一個重載了 operator() 的函數對象。以 hash<int> 為例，其源碼極為簡潔：

struct hash<int> {
    size_t operator()(int __x) const { return __x; }
};

SGI STL 內建支援的類型包括：char*、const char*、char、unsigned char、signed char、short、unsigned short、int、unsigned int、long、unsigned long。若鍵為上述類型之一，可直接使用預設哈希函數。

自定義哈希函數

對於 std::string 或自定義結構體，必須自行實現哈希函數。以 string 為例，常見實現有兩種：

// 手寫簡單哈希
struct str_hash {
    size_t operator()(const string& str) const {
        unsigned long __h = 0;
        for (size_t i = 0; i < str.size(); ++i)
            __h = 5 * __h + str[i];
        return size_t(__h);
    }
};

// 利用 STL 內部字符串哈希函數
struct str_hash {
    size_t operator()(const string& str) const {
        return __stl_hash_string(str.c_str());
    }
};

編寫自定義哈希函數的要點：

1. 使用 struct 並重載 operator()。
2. 返回類型為 size_t，參數為需哈希的鍵類型（通常為 const Key&）。
3. 成員函數應標記為 const。

二、比較函數（鍵值相等判斷）

hash_map 在處理哈希衝突時，需比較桶內元素的鍵與查找鍵是否相等，因此需要一個「相等判斷」函數對象，預設為 equal_to<Key>。其源碼如下：

template <class _Tp>
struct equal_to : public binary_function<_Tp, _Tp, bool> {
    bool operator()(const _Tp& __x, const _Tp& __y) const {
        return __x == __y;
    }
};

若鍵為自定義類型（如 struct mystruct 或 const char*），需提供相應的比較邏輯，主要有兩種方式：

方式 1：重載 operator==，配合預設 equal_to

struct mystruct {
    int iID;
    int len;
    bool operator==(const mystruct& my) const {
        return (iID == my.iID) && (len == my.len);
    }
};
// 直接使用 equal_to<mystruct>

方式 2：自定義函數對象

例如針對 const char* 使用 strcmp：

struct compare_str {
    bool operator()(const char* p1, const char* p2) const {
        return strcmp(p1, p2) == 0;
    }
};

// 使用示例
typedef hash_map<const char*, string, str_hash, compare_str> StrIntMap;
StrIntMap namemap;
namemap["岳不群"] = "華山派掌門人，人稱君子劍";
namemap["張三豐"] = "武當掌門人，太極拳創始人";
namemap["東方不敗"] = "第一高手，葵花寶典";

三、在 hash_map 中使用自定義類型完整示例

以下示範如何為自定義類 ClassA 定義哈希函數與相等函數，並正確聲明 hash_map：

#include <hash_map>
#include <string>
#include <iostream>
using namespace std;

// 自定義類
class ClassA {
public:
    ClassA(int a) : c_a(a) {}
    int getvalue() const { return c_a; }
    void setvalue(int a) { c_a = a; }
private:
    int c_a;
};

// 1. 定義哈希函數
struct hash_A {
    size_t operator()(const ClassA& A) const {
        return A.getvalue(); // 簡單以內部 int 值為哈希值
    }
};

// 2. 定義相等函數
struct equal_A {
    bool operator()(const ClassA& a1, const ClassA& a2) const {
        return a1.getvalue() == a2.getvalue();
    }
};

int main() {
    // 聲明 hash_map，模板參數依次為：Key, Value, HashFunc, EqualFunc
    hash_map<ClassA, string, hash_A, equal_A> hmap;

    ClassA a1(12);
    hmap[a1] = "I am 12";
    ClassA a2(198877);
    hmap[a2] = "I am 198877";

    cout << hmap[a1] << endl; // 輸出: I am 12
    return 0;
}

總結

掌握 hash_map 的關鍵在於理解哈希函數與相等函數的角色。對於內建類型，預設實現足夠；對於自定義類型，必須提供符合要求的函數對象。正確配置這兩個組件，即可充分發揮哈希表的高效能優勢。