在C++ STL中的unordered_map hash_function()函数

在C++中的标准模板库（STL）提供了一个非常有用的数据结构，称为unordered_map，它是一个关联容器，底层是一个哈希表，可以存储任意类型的数据。在unordered_map中，可以使用自己定义的哈希函数（hash function）来自定义键的哈希值。在这篇文章中，我们将介绍如何使用hash_function函数来自定义unordered_map的哈希函数，以及如何为不同的数据类型提供特定的哈希函数。

unordered_map概述

unordered_map是一个关联容器，允许使用键值对来管理和存储数据。unordered_map是使用哈希表来实现的，它在存储和搜索数据方面的效率比较高。下面是一个unordered_map的示例代码：

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> mymap = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };

    std::cout << "mymap contains:";
    for (auto& x: mymap) {
        std::cout << " {" << x.first << ": " << x.second << "}";
    }
    std::cout << std::endl;

    return 0;
}

在上面的代码中，我们使用了一个unordered_map来存储一些水果和它们的编号。然后，我们遍历unordered_map，输出其中的所有key-value对。运行上面的代码，将得到以下输出：

mymap contains: {cherry: 3} {apple: 1} {banana: 2}

在unordered_map中，插入和查找操作的时间复杂度都是O(1)，因此它非常适合用于需要快速查找数据的场合。

自定义哈希函数

在unordered_map中，可以使用自定义的哈希函数来定义键的哈希值。默认情况下，std::hash函数会计算键的哈希值。例如，在下面的代码中，我们使用默认的哈希函数来计算字符串”hello”的哈希值：

#include <iostream>
#include <functional>

int main()
{
    std::string s = "hello";
    std::hash<std::string> hasher;
    std::size_t hash = hasher(s);
    std::cout << "hash of " << s << ": " << hash << std::endl;
    return 0;
}

运行上面的代码，将得到以下输出：

hash of hello: 18107579207222592729

事实上，std::hash通常是一个比较好的哈希函数。但是，在某些情况下，我们可能需要使用自己定义的哈希函数来实现更好的性能或更佳的方法。事实上，在C++11之前，std::hash就是使用最简单的方式来计算哈希值，在C++11中也是如此。因此，我们可以通过自定义哈希函数来提高性能或实现更加定制化的功能。在unordered_map中，我们可以使用hash_function函数来自定义哈希函数。

hash_function函数是一个函数对象，可以接受任意类型的参数并返回一个哈希值。在unordered_map中，我们可以使用hash_function函数来指定键类型的哈希函数。下面是一个使用自定义哈希函数的unordered_map的示例代码：

#include <unordered_map>
#include <iostream>

struct Node {
    int x;
    int y;

    bool operator==(const Node& other) const {
        return x == other.x && y == other.y;
    }
};

namespace std {
    template<>
    struct hash<Node> {
        std::size_t operator()(const Node& n) const {
            return std::hash<int>()(n.x) ^ std::hash<int>()(n.y);
        }
    };
}

int main()
{
    std::unordered_map<Node, int> mymap = {
        {{1, 2}, 1},
        {{3, 4}, 2},
        {{5, 6}, 3}
    };

    std::cout << "mymap contains:";
    for (auto& x: mymap) {
        std::cout << " {" << x.first.x << ", " << x.first.y << ": " << x.second << "}";
    }
    std::cout << std::endl;

    return 0;
}

在上面的代码中，我们定义了一个结构体Node，用来表示平面上的一个点。然后，我们为Node定义了一个自定义的哈希函数，该哈希函数通过对Node中的x和y进行异或运算来生成哈希值。然后，我们使用该自定义哈希函数来创建了一个存储Node和int的unordered_map。运行上面的代码，将得到以下输出：

mymap contains: {1, 2: 1} {3, 4: 2} {5, 6: 3}

在实现自定义哈希函数时，我们需要确保哈希函数返回的哈希值是唯一的，并且最好能够均匀地分散在哈希表中的所有桶中，这样才能确保unordered_map的性能最佳。

为不同的数据类型提供哈希函数

在使用unordered_map时，我们还需要确保使用的哈希函数适用于键的数据类型。通常，STL中提供了许多内置类型（如整数，浮点数和字符串等）的默认哈希函数，但对于自定义类型，我们需要自己编写哈希函数。下面是一些示例，展示如何为不同的数据类型提供哈希函数。

字符串

对于std::string类型，可以使用std::hash函数来计算哈希值，如下所示：

#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> mymap = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };

    std::cout << "mymap contains:";
    for (auto& x: mymap) {
        std::cout << " {" << x.first << ": " << x.second << "}";
    }
    std::cout << std::endl;

    return 0;
}

数组

对于数组，可以使用std::hash函数并结合std::size函数来计算哈希值，如下所示：

#include <unordered_map>
#include <iostream>
#include <array>

int main()
{
    std::unordered_map<std::array<int, 3>, int> mymap = {
        {{1, 2, 3}, 1},
        {{4, 5, 6}, 2},
        {{7, 8, 9}, 3}
    };

    std::cout << "mymap contains:";
    for (auto& x: mymap) {
        std::cout << " {[" << x.first[0] << ", " << x.first[1] << ", " << x.first[2] << "]: " << x.second << "}";
    }
    std::cout << std::endl;

    return 0;
}

结构体

对于自定义结构体，我们需要为其定义一个专门的哈希函数。例如，下面是一个自定义结构体Point，并为其提供了一个哈希函数：

#include <unordered_map>
#include <iostream>

struct Point {
    int x;
    int y;
};

// 哈希函数
namespace std {
    template <>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return std::hash<int>()(p.x) ^ std::hash<int>()(p.y);
        }
    };
}

int main()
{
    std::unordered_map<Point, int> mymap = {
        {{1, 2}, 1},
        {{3, 4}, 2},
        {{5, 6}, 3}
    };

    std::cout << "mymap contains:";
    for (auto& x: mymap) {
        std::cout << " {(" << x.first.x << ", " << x.first.y << "): " << x.second <<"}";
    }
    std::cout << std::endl;

    return 0;
}

结论

在C++ STL中的unordered_map容器提供了一个非常有用和高效的数据结构，用于管理任意类型的数据。在unordered_map中，STL提供了默认的哈希函数，但也允许用户自己定义哈希函数，以适应特定的数据类型。通过使用hash_function函数，我们可以轻松地自定义unordered_map中的哈希函数，并提高unordered_map的性能和使用简便程度。