C++ 哈希表（Hash Table）教程

哈希表（Hash Table）是一种高效的数据结构，它通过哈希函数将键（Key）映射到存储位置，从而实现快速的插入、删除和查找操作。在平均情况下，这些操作的时间复杂度接近 O(1)。

哈希表的基本概念

1. 哈希函数（Hash Function）：将键映射到哈希表中的索引位置
2. 桶（Bucket）：哈希表中存储数据的单元
3. 碰撞（Collision）：不同的键通过哈希函数得到相同的索引
4. 负载因子（Load Factor）：哈希表中元素数量与桶数量的比值

C++ 中的哈希表实现

C++ 标准库提供了 unordered_map 和 unordered_set 两种哈希表实现：

• unordered_map：存储键值对（key-value pairs）
• unordered_set：仅存储键（keys）

1. unordered_map 的基本使用

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个存储字符串到整数的哈希表
    std::unordered_map<std::string, int> myMap;
    
    // 插入元素
    myMap["apple"] = 5;
    myMap["banana"] = 3;
    myMap["cherry"] = 7;
    
    // 使用 insert 方法插入
    myMap.insert({"date", 2});
    
    // 查找元素
    std::string key = "banana";
    auto it = myMap.find(key);
    if (it != myMap.end()) {
        std::cout << "Found " << key << ": " << it->second << std::endl;
    } else {
        std::cout << key << " not found" << std::endl;
    }
    
    // 遍历哈希表
    std::cout << "\nAll elements in the map:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 删除元素
    myMap.erase("cherry");
    std::cout << "\nAfter removing cherry:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 检查大小和是否为空
    std::cout << "\nSize of map: " << myMap.size() << std::endl;
    std::cout << "Is map empty? " << (myMap.empty() ? "Yes" : "No") << std::endl;
    
    // 清空哈希表
    myMap.clear();
    std::cout << "After clear, size: " << myMap.size() << std::endl;
    
    return 0;
}

2. unordered_set 的基本使用

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    // 创建一个存储字符串的哈希集合
    std::unordered_set<std::string> mySet;
    
    // 插入元素
    mySet.insert("apple");
    mySet.insert("banana");
    mySet.insert("cherry");
    mySet.insert("apple"); // 重复元素不会被插入
    
    // 查找元素
    std::string value = "banana";
    auto it = mySet.find(value);
    if (it != mySet.end()) {
        std::cout << "Found " << value << std::endl;
    } else {
        std::cout << value << " not found" << std::endl;
    }
    
    // 遍历哈希集合
    std::cout << "\nAll elements in the set:" << std::endl;
    for (const auto& item : mySet) {
        std::cout << item << std::endl;
    }
    
    // 删除元素
    mySet.erase("cherry");
    std::cout << "\nAfter removing cherry:" << std::endl;
    for (const auto& item : mySet) {
        std::cout << item << std::endl;
    }
    
    // 检查大小和是否为空
    std::cout << "\nSize of set: " << mySet.size() << std::endl;
    std::cout << "Is set empty? " << (mySet.empty() ? "Yes" : "No") << std::endl;
    
    // 清空哈希集合
    mySet.clear();
    std::cout << "After clear, size: " << mySet.size() << std::endl;
    
    return 0;
}

3. 自定义哈希函数

对于自定义类型，需要提供哈希函数和相等比较函数：

#include <iostream>
#include <unordered_map>
#include <string>

// 自定义类型
struct Person {
    std::string name;
    int age;
    
    Person(std::string n, int a) : name(n), age(a) {}
};

// 自定义相等比较函数
bool operator==(const Person& p1, const Person& p2) {
    return p1.name == p2.name && p1.age == p2.age;
}

// 自定义哈希函数
namespace std {
    template<> struct hash<Person> {
        size_t operator()(const Person& p) const {
            // 组合 name 和 age 的哈希值
            size_t h1 = hash<std::string>()(p.name);
            size_t h2 = hash<int>()(p.age);
            
            // 简单的哈希组合方式
            return h1 ^ (h2 << 1);
        }
    };
}

int main() {
    std::unordered_map<Person, std::string> personJobs;
    
    personJobs[Person("Alice", 30)] = "Engineer";
    personJobs[Person("Bob", 25)] = "Designer";
    personJobs[Person("Charlie", 35)] = "Manager";
    
    // 查找
    Person alice("Alice", 30);
    auto it = personJobs.find(alice);
    if (it != personJobs.end()) {
        std::cout << alice.name << " is a " << it->second << std::endl;
    }
    
    // 遍历
    std::cout << "\nAll people:" << std::endl;
    for (const auto& pair : personJobs) {
        std::cout << pair.first.name << " (" << pair.first.age << "): " 
                  << pair.second << std::endl;
    }
    
    return 0;
}

哈希表 vs 有序映射（map）

哈希表的应用场景

1. 缓存实现（如 LRU 缓存）
2. 去重操作
3. 快速查找（字典、索引）
4. 计数问题（频率统计）
5. 数据库索引

哈希表是 C++ 中处理快速查找、插入和删除操作的理想选择，在大多数情况下，unordered_map 和 unordered_set 能够提供比有序容器更好的性能。