C++：哈希函数和桶

哈希函数

哈希函数是用于将任意长度的数据（如字符串、整数数组等）映射到固定长度的值（即哈希值）的函数。这个映射过程旨在尽量减少不同输入数据产生相同哈希值（即哈希冲突）的可能性。C++标准库中的容器unordered_set、unordered_map等内部就使用了哈希函数来管理元素。

自定义类型的哈希函数

有一个简单的Point类，它有两个int类型的成员变量x和y。
Point类定义了一个内部的Hash结构体，它重载了()操作符以提供哈希函数。
在std命名空间中特化了std::hash模板，以便unordered_map等容器能够使用它。

#include <iostream>  
#include <unordered_map>  
#include <functional> // 包含std::hash  
  
// 自定义的Point类  
class Point {  
public:  
    int x, y;  
  
    Point(int x, int y) : x(x), y(y) {}  
  
    // 为了让Point可以用于unordered_map等容器中，我们需要提供哈希函数  
    struct Hash {  
        size_t operator()(const Point& p) const {  
            std::hash<int> int_hasher;  
            // 这里简单地使用两个成员变量的哈希值进行异或运算，但实际应用中可能需要更复杂的哈希算法  
            // 以减少哈希冲突的可能性  
            return int_hasher(p.x) ^ (int_hasher(p.y) << 1);  
        }  
    };  
  
    // 也可以重载==操作符，以便unordered_map能够比较Point对象  
    bool operator==(const Point& other) const {  
        return x == other.x && y == other.y;  
    }  
};  
  
namespace std {  
    // 特化std::hash模板以支持Point类型  
    template<>  
    struct hash<Point> {  
        size_t operator()(const Point& p) const {  
            // 这里直接使用Point类内部定义的Hash结构体的哈希函数  
            return Point::Hash()(p);  
        }  
    };  
}  
  
int main() {  
    // 使用unordered_map存储Point对象到字符串的映射  
    std::unordered_map<Point, std::string> pointMap;  
  
    // 插入元素  
    pointMap[Point(1, 2)] = "Point(1, 2)";  
    pointMap[Point(3, 4)] = "Point(3, 4)";  
  
    // 访问并打印元素  
    for (const auto& pair : pointMap) {  
        std::cout << "(" << pair.first.x << ", " << pair.first.y << "): " << pair.second << std::endl;  
    }  
  
    return 0;  
}

桶

"桶"可以理解为哈希表中用于存储元素的基本单元或位置。
1.定义与功能：

• 桶是哈希表中用于存储元素的容器，每个桶可以包含零个或多个元素。
• 当向unordered_map中插入一个元素时，会根据元素的键（key）计算出一个哈希值，然后基于这个哈希值将元素放入对应的桶中。
• 如果多个元素的哈希值相同（即发生了哈希冲突），这些元素会被存储在同一个桶中，但通常通过链表或其他数据结构来区分它们。

2.内部实现：

• unordered_map通常使用链表法（也称为链地址法）来解决哈希冲突。即，在同一个桶中的元素通过链表连接起来。
• 桶的数量（即哈希表的大小）在unordered_map的初始化时可以指定，并且随着元素的增加，unordered_map可能会自动扩容以增加桶的数量，从而降低哈希冲突的概率，提高性能。

3.扩容机制：

• 当unordered_map中的元素数量超过其容量的一定比例（即负载因子超过了阈值）时，会触发扩容操作。
• 扩容时，会重新计算所有元素的哈希值，并将它们重新分配到新的、更大的哈希表中。

4.桶的大小与性能：

• 桶的大小（即哈希表的大小）直接影响到unordered_map的性能。过小的桶数会增加哈希冲突的概率，从而降低查找和插入的效率。
• 然而，过大的桶数也会浪费内存空间，并且可能增加查找时的遍历时间（尽管这通常不是主要问题，因为哈希表的设计就是尽量减少遍历）。

哈希表

哈希表（Hash Table）是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。它通过哈希函数将键（Key）映射到表中一个位置来访问记录，以加快查找的速度。这个映射过程可以极大地减少查找时间，平均情况下接近常数时间复杂度。

桶

在哈希表的上下文中，桶（Bucket）是用于存储具有相同哈希值的键值对（Key-Value Pair）的容器。由于哈希函数可能将不同的键映射到相同的哈希值（即哈希冲突），因此需要使用桶来存储这些冲突的键值对。桶通常是通过链表、红黑树或其他数据结构来实现的，以便在同一桶内高效地管理和检索多个键值对。

关系

• 映射关系：哈希表通过哈希函数将键映射到桶的索引上。这个索引决定了键值对应该存储在哪个桶中。
• 冲突解决：当哈希冲突发生时（即多个键具有相同的哈希值），这些键对应的键值对会被存储在同一个桶中。桶内部的数据结构（如链表）用于区分这些冲突的键值对。
• 性能影响：桶的数量和大小直接影响哈希表的性能。如果桶的数量太少，哈希冲突的概率会增加，从而降低查找和插入的效率。相反，如果桶的数量过多，则会浪费内存空间。因此，哈希表通常会在负载因子（即元素数量与桶数量的比例）达到一定阈值时进行扩容，以增加桶的数量并降低哈希冲突的概率。

总结

哈希表和桶是相辅相成的概念。哈希表通过哈希函数将键映射到桶的索引上，并使用桶来存储具有相同哈希值的键值对。桶内部的数据结构用于解决哈希冲突，并允许在同一桶内高效地管理和检索多个键值对。这种设计使得哈希表能够支持快速的插入、删除和查找操作，是许多高效算法和数据结构的基础。