std::hash——STL中的哈希函數

哈希函數在計算機科學中扮演着重要的角色，可用於實現數據存儲、緩存等常用技術。在C++的STL庫中，std::hash作為哈希函數的實現，提供了快速而簡單的哈希算法。本文將從多個方面闡述std::hash的相關知識，為讀者帶來深入了解。

一、std::hash的基本用法

#include 
#include 
#include 

int main() {
    std::unordered_map myMap;
    myMap["apple"] = 1;
    myMap["banana"] = 2;
    myMap["cat"] = 3;
    
    std::hash hasher;
    std::cout << "Hash value of 'apple': " << hasher("apple") << std::endl;
    
    return 0;
}

如上述代碼所示，std::hash是一個模板類，模板參數為被哈希的數據類型。在使用時，我們需要創建一個std::hash對象，並將待哈希的數據作為其參數傳入，得到該數據的哈希值。

上述代碼中，我們創建了一個std::unordered_map對象，並存入三組鍵值對。創建std::hash對象後，我們使用其計算了字符串”apple”的哈希值，將其輸出至控制台。運行該段代碼，輸出結果為：

Hash value of 'apple': 3032715092448685573

可以看到，std::hash計算出來的哈希值是一個長整型的數值，用於表示該數據在哈希表中的位置。

二、自定義類型的哈希函數

std::hash模板類默認支持對大部分基本數據類型（例如整型、浮點型等）的哈希計算，同時如果需要對某個自定義類型進行哈希，可以通過提供一個哈希函數的實現來實現該功能。以下是一個自定義類型的示例：

struct Student {
    std::string name;
    int age;
    bool gender;
};

namespace std {
    template 
    struct hash {
        size_t operator()(const Student& s) const {
            return std::hash()(s.name) ^ std::hash()(s.age) ^ std::hash()(s.gender);
        }
    };
}

int main() {
    std::unordered_map myMap;
    myMap[{"Tom", 20, true}] = 1;
    myMap[{"Lucy", 21, false}] = 2;
    
    for (auto& [k, v] : myMap) {
        std::cout << "Name: " << k.name << " Age: " << k.age << " Gender: " << k.gender << " Value: "
        << v << std::endl;
    }
    
    return 0;
}

如上述代碼所示，我們首先定義了一個Student結構體，其包含三個成員分別為姓名、年齡和性別。然後我們為該結構體提供了哈希函數的實現，該哈希函數使用異或運算符將姓名、年齡和性別三個數據分別計算哈希值併合並。

在主函數中，我們創建了一個std::unordered_map對象，並存入兩個Student對象。值得注意的是，我們可以直接使用”{“和”}”來創建一個Student對象，這些語法是C++17的新特性。

最後，我們對哈希表中的每個對象進行遍歷，並將Student成員的值輸出至控制台。運行該段代碼，輸出結果為：

Name: Lucy Age: 21 Gender: 0 Value: 2
Name: Tom Age: 20 Gender: 1 Value: 1

可以看到，我們成功地將Student對象作為哈希表的鍵，並且得到了正確的輸出結果。

三、std::hash的性能和衝突處理

哈希函數的性能是我們重點關注的部分之一，因為哈希表的性能往往會直接影響程序的執行效率。std::hash的性能取決於其計算算法的效率，同時也與哈希表的大小、被哈希的數據的分佈情況等密切相關。

在處理哈希衝突方面，std::hash使用了拉鏈法（Chaining）來解決衝突。在拉鏈法中，哈希表的每個桶中存放着一個鏈表，若多個數據的哈希值映射到同一個桶中，則將這些數據存儲在鏈表中。當需要訪問某個數據時，先根據其哈希值定位到該桶，然後遍歷該桶中的鏈表，找到對應的數據。

以下代碼演示了哈希表中的衝突處理過程，以及哈希表大小對性能的影響：

#include 
#include 
#include 

int main() {
    std::unordered_map myMap;
    for (int i = 0; i < 50000; ++i) {
        myMap[i] = i;
    }
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 50000; ++i) {
        myMap[i];
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration diff = end - start;
    std::cout << "Time taken on 50k elements: " << diff.count() << " seconds" << std::endl;
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 500000; ++i) {
        myMap[i];
    }
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "Time taken on 500k elements: " << diff.count() << " seconds" << std::endl;
    
    std::unordered_map myMap2;
    for (int i = 0; i < 50000; ++i) {
        myMap2[i] = i;
    }
    myMap2.reserve(100000);
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 50000; ++i) {
        myMap2[i];
    }
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "Time taken on 50k elements with capacity: " << diff.count() << " seconds" << std::endl;
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 500000; ++i) {
        myMap2[i];
    }
    end = std::chrono::high_resolution_clock::now();
    diff = end - start;
    std::cout << "Time taken on 500k elements with capacity: " << diff.count() << " seconds" << std::endl;
    
    return 0;
}

通過上述代碼，我們創建了兩個哈希表myMap和myMap2，它們分別包含了50000和500000個元素。我們使用std::chrono庫來測量對這兩個哈希表中元素的訪問時間，其中myMap2事先被調用了reserve函數，其容量為100000。

運行該段代碼，輸出結果為：

Time taken on 50k elements: 0.000267165 seconds
Time taken on 500k elements: 0.00288509 seconds
Time taken on 50k elements with capacity: 7.302e-06 seconds
Time taken on 500k elements with capacity: 7.95873e-05 seconds

可以看到，在沒有reserve函數預先分配哈希表容量的情況下，訪問500000個數據需要耗費2.88秒的時間；而在預先分配容量的情況下，訪問500000個數據的耗時僅為0.000795873秒，大大提高了程序的性能。

此外，哈希表的負載因子（load factor）是衡量哈希表性能的重要指標之一。負載因子的計算公式為hashtable.size()/hashtable.bucket_count()，表示哈希表中鍵值對的數量與哈希表的容量之比。當哈希表的負載因子接近於1時，意味着哈希衝突較多，查詢效率會受到很大影響。因此在實際應用中，我們應該儘可能保持哈希表的負載因子在一個合理的範圍內。

四、std::hash的局限性

std::hash計算出的哈希值是一個長整型的數值，其佔用空間較大。在有些情況下，我們需要將哈希值轉換為指定的數據類型。這時我們可以使用std::hash_combine函數，該函數將多個哈希值合併為一個，從而生成一個新的哈希值。以下是一個使用std::hash_combine的例子：

#include 
#include 

template 
void hash_combine(std::size_t& seed, const T& val) {
    seed ^= std::hash()(val) + 0x9e3779b9 + (seed <> 2);
}

int main() {
    std::string s1 = "hello";
    std::string s2 = "world";
    std::size_t h1 = std::hash{}(s1);
    std::size_t h2 = std::hash{}(s2);
    std::size_t combined_hash = 0;
    hash_combine(combined_hash, h1);
    hash_combine(combined_hash, h2);
    std::cout << "Combined hash: " << combined_hash << std::endl;
    
    return 0;
}

在上述代碼中，我們定義了一個hash_combine函數，使用XOR運算符將多個哈希值合併。在主函數中，我們計算了兩個字符串的哈希值，並使用hash_combine函數將其合併。最終輸出的哈希值為：

Combined hash: 4820441328262842544

除此之外，std::hash還存在其他的一些局限性，例如它不能處理無法比較相等的對象、不能處理重載了&運算符的類型等。在這些情況下，我們需要手動提供哈希函數的實現。

五、小結

本文詳細介紹了std::hash在C++中的基本用法、自定義類型的哈希函數實現方法、哈希表的性能與衝突處理、哈希值合併以及std::hash的局限性等方面的知識點。通過本文的學習，讀者可以更全面、深入地理解C++ STL中哈希函數的實現。