C++ STL hash 哈希函数（哈希函数c语言）

01

引言

在C++中，std::hash是标准库中提供的一个模板结构，用于提供基本的哈希函数功能。std::hash可以用于自定义数据类型的哈希值计算，以便这些类型可以被用在基于哈希的容器中，如std::unordered_map、std::unordered_set等。

02

基本类型

std::hash 是 C++ 标准库中的一个模板类，它提供了一个默认的哈希函数。对于大多数基本数据类型，比如 int、float、double、char 等，C++ 标准库已经提供了 std::hash 的特化版本。然而，对于自定义类型，你需要自己特化这个模板。

std::hash 模板的基本原型如下：

namespace std {
    template <class T>
    struct hash {
        size_t operator()(const T& val) const;
    };
}


namespace std {
    template <>
    struct hash<int> {
        std::size_t operator()(const int& key) const;
    };
}


namespace std {
    template <>
    struct hash<MyClass> {
        std::size_t operator()(const MyClass& key) const;
    };
}

这里：

• T 是你想要为其生成哈希值的数据类型。
• operator() 是模板结构的成员函数，它接受一个类型为 const T& 的参数，并返回一个 size_t 类型的哈希值。

对于标准库中已经特化的基本类型，std::hash 的实现通常依赖于这些类型的底层表示，以生成哈希值。

03

使用方法

std::hash的基本用法如下：

#include <iostream>
#include <functional> // 包含 std::hash


int main() {
    std::hash<int> hashInt;
    int value = 10;
    size_t hashedValue = hashInt(value); // 计算value的哈希值


    std::cout << "The hash value of " << value << " is " << hashedValue << std::endl;


    return 0;
}
// The hash value of 10 is 10

04

自定义哈希函数

对于自定义类型，你可能需要特化std::hash，以提供适合你类型的哈希函数。例如：

#include <functional>
#include <iostream>


struct Point {
    int x, y;
};


// 特化 std::hash 以适用于 Point 类型
namespace std {
    template<>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ hash<int>()(p.y);
        }
    };
}


int main() {
    Point p = {1, 2};
    size_t hashedValue = std::hash<Point>()(p);
    std::cout << "The hash value of Point(1, 2) is " << hashedValue << std::endl;


    return 0;
}
// The hash value of Point(1, 2) is 3

在这个例子中，我们为Point结构体特化了std::hash，使其能够计算Point对象的哈希值。注意，哈希函数应该是确定的，即对于相同的输入，它应该总是返回相同的哈希值。

注意：

• std::hash的实现通常依赖于模板参数类型的operator()，如果自定义类型没有提供operator()，那么std::hash将无法使用。此外，哈希函数应该尽可能均匀地分布哈希值，以避免哈希表中的冲突。
• 在特化版本中，一般使用异或和一些简单的位操作来组合 a 和 b 的哈希值，以生成 MyType 的哈希值。这是一种常见的技术，用于组合多个字段的哈希值来创建一个复合类型的哈希值。

05

小结

std::hash 是 C++ STL 中的一个模板类，它提供了一种机制来生成一个类型 T 的哈希值。这个哈希值可以用于哈希表（如 std::unordered_map、std::unordered_set 等）的键值对映射中。

以下是 std::hash 的一些关键点：

1. 头文件：std::hash 定义在 <functional> 头文件中。
2. 命名空间：std::hash 位于 std 命名空间中。
3. 特化：C++ STL 为许多基本类型（如 int、float、double、std::string 等）提供了 std::hash 的特化版本。这意味着这些类型可以直接使用 std::hash 来生成哈希值。
4. 自定义类型：对于自定义类型，您需要为该类型特化 std::hash，以提供自定义的哈希函数。这通常涉及到定义一个重载的 operator()，该函数接受自定义类型的实例，并返回一个 size_t 类型的哈希值。

std::hash 是实现高效哈希表的关键组件，它允许开发者利用 C++ STL 提供的哈希表容器。