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中哈希函数的实现。