LuLu
LuLu/C++/
Hash
Search
Hash

Hash

Created
Jun 13, 2024 03:02 PM
Tags
在C++中，标准库已经提供了 std::hash 函数来计算内置类型的哈希值。然而，当你想要将自定义结构作为 unordered_map 的键时，需要自定义两个函数：一个哈希函数和一个比较函数。

1. 内置类型的哈希计算

C++ 标准库已经提供了 std::hash 函数来计算字符串等内置类型的哈希值。以下示例演示了如何使用 std::hash 对字符串进行哈希计算：
#include <iostream>
#include <iomanip>
#include <functional>
#include <string>
int main() {
    std::string str = "Meet the new boss...";
    std::size_t str_hash = std::hash<std::string>{}(str);
    std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << '\n';
    return 0;
}

2. 自定义结构的哈希计算

如果要对自定义结构求哈希键，需要定义两个函数：一个哈希函数和一个比较函数。

自定义结构和比较函数

首先，定义一个自定义结构并重载 == 操作符，以便比较两个对象是否相等：
#include <iostream>
#include <unordered_map>
// 定义自定义结构
struct MyStruct {
    int x;
    int y;

    // 重载==操作符用于比较两个MyStruct对象是否相等
    bool operator==(const MyStruct& other) const {
        return x == other.x && y == other.y;
    }
};

自定义哈希函数

接下来，提供一个自定义哈希函数，用于计算 MyStruct 对象的哈希值：
#include <functional> 
// 引入
std::hashstruct MyStructHash {
    std::size_t operator()(const MyStruct& s) const noexcept {
        std::size_t h1 = std::hash<int>{}(s.x);
        std::size_t h2 = std::hash<int>{}(s.y);
        return h1 ^ (h2 << 1); // 使用异或和位移组合两个哈希值
    }
};

3. 使用 unordered_map 存储自定义结构

现在，我们可以将 MyStruct 用作 unordered_map 的键：
int main() {
    // 使用MyStruct作为unordered_map的key
    std::unordered_map<MyStruct, std::string, MyStructHash> myMap;

    // 插入一些数据
    myMap[{1, 2}] = "Value1";
    myMap[{3, 4}] = "Value2";

    // 访问并打印数据
    std::cout << "Key (1,2): " << myMap[{1, 2}] << std::endl;
    std::cout << "Key (3,4): " << myMap[{3, 4}] << std::endl;

    return 0;
}

4. 另一种定义哈希函数的方法

除了定义自定义哈希函数，还可以通过特化 std::hash 来实现，这样可以更好地集成到标准库中：
#include <functional> 
// 引入 std::hash// 定义自定义结构
struct S {
    std::string first_name;
    std::string last_name;
};

bool operator==(const S& lhs, const S& rhs) {
    return lhs.first_name == rhs.first_name && lhs.last_name == rhs.last_name;
}

// 自定义std::hash的特化版本
namespace std {
    template<>
    struct hash<S> {
        std::size_t operator()(S const& s) const noexcept {
            std::size_t h1 = std::hash<std::string>{}(s.first_name);
            std::size_t h2 = std::hash<std::string>{}(s.last_name);
            return h1 ^ (h2 << 1); // 使用异或和位移组合两个哈希值
        }
    };
}

int main() {
    S obj = { "Hubert", "Farnsworth" };

    // 使用特化的 std::hash<S> 计算哈希值
    std::cout << "hash(" << std::quoted(obj.first_name) << ", "
              << std::quoted(obj.last_name) << ") = "
              << std::hash<S>{}(obj) << '\n';

    // 使用自定义类型作为 unordered_set 的键
    std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Turanga", "Leela"}};
    for (const auto& s : names)
        std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n';

    return 0;
}

总结

通过定义自定义结构的哈希函数和比较函数，你可以将自定义类型用作 unordered_map 和 unordered_set 的键。这使得在 C++ 中处理复杂数据类型更加灵活和高效。
/
Copyright 2024 lulu