哈希（Hash）核心概念与 C++ 应用

一、哈希的核心概念

1. 哈希到底是什么？

先回忆两个基础数据结构的痛点：

数组：支持下标 O(1) 查找，但只能通过「连续数字下标」访问，无法通过「任意数据（如字符串、自定义对象）」快速查找；
链表：支持任意数据存储，但查找/删除需要从头遍历，时间复杂度 O(n)，数据量越大越慢。

哈希的核心解决思路：

定义一个「映射规则」（哈希函数），把 任意类型的原始数据 (key) 转换成一个 整型数字（哈希值），然后用这个哈希值作为「数组下标」存储数据。

最终效果：查找/插入/删除的平均时间复杂度都是 O(1)，和数据量无关，极致高效！

2. 哈希的核心基础概念

概念 1：哈希函数 (Hash Function)

定义：把任意输入值（key）映射成固定范围整型值（哈希值）的函数，记为 hash(key) = value。

核心要求

确定性：同一个 key，永远得到同一个哈希值（绝对不能同一个 key，这次算出来是 5，下次是 8）；
高效性：计算哈希值的速度要快，不能比查找本身还耗时；
均匀性：尽量让不同的 key 映射到不同的哈希值，减少冲突。

C++ 中常见的哈希函数

取模法：hash(key) = key % 数组长度（最基础，比如学号 1001，模 10 得到哈希值 1）；
直接定址法：hash(key) = key（比如 key 是整型 ID，直接用 ID 当下标）；
字符串哈希：将字符串的每个字符转成数字，通过加权求和得到哈希值（C++ 标准库对 string 的哈希就是这种实现）。

概念 2：哈希表 (Hash Table)

定义：哈希的底层存储结构，本质是「数组 + 冲突解决结构」。

我们把哈希函数计算出的哈希值，作为数组的「下标」，这个数组的每个位置称为「桶（bucket）」，数据就存在对应的桶里。

如果没有哈希冲突，哈希表就是一个简单的数组，所有操作都是 O(1)。

概念 3：哈希冲突 (Hash Collision)

1. 什么是哈希冲突？

白话解释：不同的原始 key，通过哈希函数计算后，得到了相同的哈希值，最终要存在哈希表的同一个桶里，这种情况就是哈希冲突。

比如：哈希函数是 hash(key) = key % 10，那么 key=1 和 key=11，计算出的哈希值都是 1，就会发生冲突。

哈希冲突是无法避免的，只能尽可能减少和解决。

原因：哈希函数是「将无限大的输入值域」映射到「有限小的哈希值范围」，就像把 1000 个苹果放进 100 个篮子，必然有篮子放多个苹果。

二、哈希冲突的核心解决方法

方法 1：拉链法 (Separate Chaining)

1. 拉链法的本质：给哈希表的每个桶挂个'链条'

拉链法是解决哈希冲突的最主流、最易实现的方案，没有之一。

它的核心思路是：

哈希表的底层是一个数组，数组的每个元素称为一个 桶（Bucket）；
每个桶不再只存一个数据，而是指向一个 链表/红黑树 的表头；
当不同的 key 计算出相同的哈希值（发生冲突）时，不会争抢同一个桶的位置，而是像挂灯笼一样，把新数据挂载到对应桶的'链条'末尾。

形象比喻：把哈希表的数组想象成一排挂钩，每个挂钩就是一个桶；冲突的数据就是一串钥匙，全挂在同一个挂钩上，互不干扰。

2. 拉链法的核心结构

哈希表数组（桶数组）
索引 0 → 桶 0 → 链表节点 (key:A, val:1) → 链表节点 (key:J, val:3) → null
索引 1 → 桶 1 → 链表节点 (key:B, val:2) → null
索引 2 → 桶 2 → null （空桶）
索引 3 → 桶 3 → 链表节点 (key:D, val:5) → 链表节点 (key:M, val:7) → 链表节点 (key:X, val:9) → null

桶数组：承载哈希值的索引，决定了哈希表的基础容量；
链条结构：早期是单向链表，C++11 后优化为 '链表 + 红黑树' 混合结构；
节点：存储 key、value 和指向下一个节点的指针。

3. 为什么 C++ 标准库选拉链法？

对比开放寻址法，拉链法的优势是工程上的'容错性'和'易用性'，这也是标准库选择它的核心原因：

特性	拉链法	开放寻址法
冲突处理难度	简单（挂链表即可）	复杂（需找空位，处理删除）
负载因子容忍度	高（>1 也能工作）	低（>0.7 性能急剧下降）
内存利用率	非连续内存，灵活分配	连续数组，易浪费空间
删除操作	直接删链表节点，无残留	需'标记删除'，易产生空洞
扩容成本	元素迁移时不影响原链条	需重新探测所有元素位置

结论：拉链法更适合作为通用哈希容器的冲突解决方案，开放寻址法仅适合内存极度紧张的嵌入式场景。

4. 拉链法的核心操作：插入、查找、删除

插入操作

输入：key 和 value

核心目标：将数据挂载到对应桶的链条上，且保证 key 唯一

步骤拆解：

计算哈希值：通过哈希函数 hash(key) 得到哈希值 h；
计算桶索引：通过取模运算得到桶的下标 index = h % 桶数组长度（取模是最基础的映射方式）；
检查冲突：遍历桶 index 对应的链表：
- 如果找到相同的 key：更新 value，结束插入；
- 如果遍历到链表末尾都没找到相同 key：执行下一步；
挂载新节点：创建新的链表节点，将节点插入到链表头部或尾部（头部插入效率更高，无需遍历到末尾）；
检查负载因子：如果 元素总数 / 桶数组长度 > 负载因子阈值（默认 0.75），触发扩容（桶数组长度翻倍，所有元素重新哈希迁移）。

头部插入 vs 尾部插入

头部插入：时间 O(1)，无需遍历链表，是工程上的首选；
尾部插入：时间 O(k)，需要遍历到链表末尾，仅在需要保持插入顺序时使用（C++ 标准库不保证顺序，所以用头部插入）。

查找操作（平均 O(1)，最坏 O(k)）

输入：要查找的 key

核心目标：找到对应桶的链条中 key 匹配的节点

步骤拆解：

计算哈希值 h 和桶索引 index（同插入步骤 1-2）；
遍历桶 index 对应的链表：
- 如果找到 key 匹配的节点：返回 value，查找成功；
- 如果遍历到链表末尾未找到：返回'不存在'，查找失败。

性能瓶颈：当链条长度 k 过大时，查找效率会从 O(1) 退化到 O(k)—— 这也是 C++ 标准库引入红黑树优化的原因。

删除操作（平均 O(1)，最坏 O(k)）

输入：要删除的 key

核心目标：从链条中移除 key 匹配的节点，保证链表结构不断裂

步骤拆解：

计算哈希值 h 和桶索引 index（同插入步骤 1-2）；
遍历桶 index 对应的链表，同时记录当前节点和前驱节点：
- 如果找到 key 匹配的节点：
  - 如果是头节点：让桶直接指向头节点的下一个节点；
  - 如果是中间/尾节点：让前驱节点的指针指向当前节点的下一个节点；
  - 释放当前节点的内存，删除成功；
- 如果遍历到链表末尾未找到：删除失败。

关键细节：必须记录前驱节点，否则删除中间节点后，链表会断裂，后续节点会'丢失'。

5. C++ 标准库的拉链法优化：链表→红黑树

C++11 中的 unordered_map/unordered_set，对拉链法做了一个革命性优化：当桶内的链表长度超过阈值（默认 8）时，自动将链表转换为红黑树；当长度低于阈值（默认 6）时，再转回链表。

为什么要做这个优化？

链表的痛点：当链条长度 k=8 时，最坏查找时间是 O(8)；当 k=100 时，退化到 O(100)，性能极差；
红黑树的优势：红黑树是平衡二叉树，最坏查找时间是 O(log k)，当 k=8 时，O(log 8)=O(3)，比链表快 2 倍多；当 k=100 时，O(log 100)≈O(7)，比链表快 14 倍。

阈值选择的原因

转红黑树阈值 = 8：经过大量实验，当链表长度超过 8 时，红黑树的 O(log k) 优势开始超过链表；
转链表阈值 = 6：设置一个'回退阈值'，避免长度在 8 附近波动时，频繁在链表和红黑树之间切换（比如长度从 8→7→8，反复转换会消耗大量性能）。

结论：这个优化让 C++ 的哈希容器，在极端冲突场景下，依然能保持高效的查找性能。

6. 手写拉链法哈希表

#include <iostream>
#include <string>
using namespace std;

// 定义链表节点结构
template <typename K, typename V>
struct HashNode {
    K key; // 键
    V value; // 值
    HashNode<K, V>* next; // 指向下一个节点的指针

    // 构造函数
    HashNode(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
};

// 简易拉链法哈希表
template <typename K, typename V>
class HashTable {
private:
    using Node = HashNode<K, V>;
    Node** buckets; // 桶数组：二级指针，指向指针数组
    size_t bucketCount; // 桶的数量
    size_t elementCount; // 元素总数
    const float loadFactorThreshold = 0.75f; // 负载因子阈值

    // 简易哈希函数：针对 string 类型（可扩展其他类型）
    size_t hashFunc(const string& key) const {
        size_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c; // 31 是质数，减少哈希冲突
        }
        return hash;
    }

    // 针对 int 类型的哈希函数
    size_t hashFunc(int key) const {
        return key;
    }

    // 计算桶索引
    size_t getBucketIndex(const K& key) const {
        return hashFunc(key) % bucketCount;
    }

    // 扩容：桶数量翻倍，所有元素重新哈希
    void resize() {
        size_t newBucketCount = bucketCount * 2;
        Node** newBuckets = new Node*[newBucketCount](); // 初始化所有桶为 nullptr

        // 遍历旧桶，将所有元素迁移到新桶
        for (size_t i = 0; i < bucketCount; ++i) {
            Node* curr = buckets[i];
            while (curr != nullptr) {
                Node* next = curr->next; // 保存下一个节点，避免迁移时丢失
                // 计算新桶索引
                size_t newIndex = hashFunc(curr->key) % newBucketCount;
                // 头部插入新桶
                curr->next = newBuckets[newIndex];
                newBuckets[newIndex] = curr;
                curr = next;
            }
            delete[] buckets[i]; // 释放旧桶的链表节点
        }

        // 替换桶数组
        delete[] buckets;
        buckets = newBuckets;
        bucketCount = newBucketCount;
    }

public:
    // 构造函数：初始化桶数组
    HashTable(size_t initBucketCount = 16) : bucketCount(initBucketCount), elementCount(0) {
        // 初始化桶数组，每个桶初始为 nullptr
        buckets = new Node*[bucketCount]();
    }

    // 析构函数：释放所有内存
    ~HashTable() {
        for (size_t i = 0; i < bucketCount; ++i) {
            Node* curr = buckets[i];
            while (curr != nullptr) {
                Node* next = curr->next;
                delete curr;
                curr = next;
            }
        }
        delete[] buckets;
    }

    // 插入/更新元素
    void put(const K& key, const V& value) {
        // 检查负载因子，触发扩容
        if (static_cast<float>(elementCount) / bucketCount > loadFactorThreshold) {
            resize();
        }
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];

        // 遍历链表，检查 key 是否存在
        while (curr != nullptr) {
            if (curr->key == key) {
                curr->value = value; // key 存在，更新 value
                return;
            }
            curr = curr->next;
        }

        // key 不存在，头部插入新节点
        Node* newNode = new Node(key, value);
        newNode->next = buckets[index];
        buckets[index] = newNode;
        elementCount++;
    }

    // 查找元素
    bool get(const K& key, V& value) {
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];
        while (curr != nullptr) {
            if (curr->key == key) {
                value = curr->value; // 找到 key，返回 value
                return true;
            }
            curr = curr->next;
        }
        return false; // key 不存在
    }

    // 删除元素
    bool remove(const K& key) {
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];
        Node* prev = nullptr; // 记录前驱节点

        while (curr != nullptr) {
            if (curr->key == key) {
                // 处理删除逻辑
                if (prev == nullptr) { // 删除头节点
                    buckets[index] = curr->next;
                } else { // 删除中间/尾节点
                    prev->next = curr->next;
                }
                delete curr;
                elementCount--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false; // key 不存在
    }

    // 获取元素总数
    size_t size() const {
        return elementCount;
    }
};

// 测试代码
int main() {
    HashTable<string, int> ht;

    // 插入元素
    ht.put("apple", 5);
    ht.put("banana", 3);
    ht.put("apple", 10); // 更新 apple 的值

    // 查找元素
    int value;
    if (ht.get("apple", value)) {
        cout << "apple: " << value << endl; // 输出 10
    }

    // 删除元素
    ht.remove("banana");
    cout << "size: " << ht.size() << endl; // 输出 1

    return 0;
}

代码核心亮点

模板化设计：支持任意 key/value 类型，通用性强；
手动扩容逻辑：严格遵循负载因子阈值，体现哈希表的核心优化思想；
头部插入策略：保证插入操作的 O(1) 时间复杂度；
内存安全：析构函数释放所有节点和桶数组，避免内存泄漏。

7. 拉链法的工程优化技巧

在实际项目中，使用拉链法哈希表（比如 unordered_map）时，掌握这些技巧能大幅提升性能：

提前 reserve 容量：如果知道数据量，初始化时调用 reserve(n)，避免多次扩容（扩容的 rehash 操作是 O(n)，很耗时）；

unordered_map<string, int> mp;
mp.reserve(10000); // 提前分配足够的桶，避免插入 10000 个元素时多次扩容

自定义高效哈希函数：标准库的 string 哈希函数在极端场景下冲突率较高，可以自定义哈希函数（比如结合 BKDRHash 等工业级哈希算法）；
避免存储大对象：在桶的链条中存储指针/引用，而非大对象，减少拷贝和内存占用；
合理设置负载因子：如果内存充足，可以手动调低负载因子（比如 0.5），进一步降低冲突概率（需通过自定义哈希表实现，标准库不支持修改）。

方法 2：开放寻址法 (Open Addressing)

原理

当发生哈希冲突时，不额外开辟空间，而是在哈希表的「其他空桶」中寻找新的存储位置，核心是「找下一个空位」。常见的寻址策略：线性探测（冲突后往后找 1 个位置）、二次探测（往后找平方数位置）、再哈希（换一个哈希函数重新计算）。

简单理解：一个桶被占了，就去隔壁桶看看，直到找到空桶。

核心优缺点

优点：不需要额外内存，空间利用率高；缓存友好（数据存在连续的数组中）；缺点：实现复杂，删除数据时不能直接清空（会导致后续查找失效），只能做「标记删除」；负载因子过高时，冲突概率急剧上升，性能退化严重；

适用场景：内存紧张的嵌入式开发、高性能缓存系统，C++ 中极少用标准库实现，一般是手写。

三、哈希的核心性能指标 + 特性

1. 哈希的核心性能指标：负载因子 (Load Factor)

定义

负载因子 α = 哈希表中存储的元素个数 / 哈希表的桶的总数。比如：哈希表有 100 个桶，存了 75 个元素，负载因子就是 0.75。

核心作用

负载因子是衡量哈希表拥挤程度的核心指标，也是哈希表「扩容」的唯一触发条件！

α 越小：桶的数量远大于元素数，冲突概率极低，性能接近纯数组的 O(1)，但空间利用率低；
α 越大：桶的数量接近元素数，冲突概率急剧上升，性能退化严重，空间利用率高；

为什么 C++ 的哈希容器默认负载因子是 0.75？

当 α ≤ 0.75 时，哈希冲突的概率极低，拉链法的链条长度基本都是 1，操作效率稳定在 O(1)；当 α > 0.75 时，冲突概率会指数级增长，链条长度快速变长，性能开始退化；

当哈希表的负载因子超过 0.75 时，C++ 会自动触发「扩容」：桶的数量翻倍，所有元素重新计算哈希值并迁移（rehash），这个过程的时间复杂度是 O(n)，但扩容是「摊还」的，整体平均复杂度还是 O(1)。

2. 哈希的核心时间复杂度

哈希表的 平均时间复杂度：查找、插入、删除都是 O(1)；

哈希表的 最坏时间复杂度：查找、插入、删除都是 O(n)；

最坏情况的触发原因：

哈希函数设计极差，所有 key 都映射到同一个哈希值，拉链法变成单链表；
恶意构造数据，让所有 key 都冲突；
负载因子过高，没有及时扩容。

3. 哈希的核心特性

无序性：哈希表的元素存储顺序和插入顺序无关，也和 key 的大小无关，因为元素的位置由哈希值决定。这是 C++ 中 unordered_* 容器和 set/map 的核心区别之一；
键的唯一性：哈希集合（unordered_set）中，同一个 key 只能存一次；哈希映射（unordered_map）中，key 是唯一的，value 可以重复；
键的不可变性：哈希容器的 key绝对不能被修改！因为 key 的哈希值是初始化时计算的，修改 key 会导致哈希值变化，元素就会「丢失」在哈希表中，无法被找到。

四、哈希容器的使用

C++ 对哈希的支持是从 C++11 开始的，提供了两个核心的哈希容器，也是项目开发中最常用的容器，没有之一。

1. C++ 哈希容器全家福：unordered_set & unordered_map

核心结论

C++ 的 unordered_set 和 unordered_map：

底层都是哈希表，采用「拉链法」解决哈希冲突；
所有操作的平均时间复杂度 O(1)，最坏 O(n)；
容器内的元素是无序的；
依赖 C++11 及以上标准，项目中必须开启 -std=c++11 编译。

哈希容器 vs 有序容器（set/map）：怎么选？

特性	unordered_set/unordered_map（哈希）	set/map（红黑树）
底层实现	哈希表 + 拉链法	红黑树（平衡二叉树）
元素顺序	无序	按键升序排列
平均时间复杂度	O(1) 极致高效	O(log n) 稳定高效
最坏时间复杂度	O(n)	O(log n) 永远稳定
内存占用	较大（空间换时间）	较小
适用场景	只需要查找/插入/删除，不需要有序	需要有序遍历、范围查询

能哈希，不树型；要有序，再树型。

简单说：只要业务不需要有序，优先用哈希容器，性能碾压红黑树容器！

2. 哈希容器的基础用法

语法极简，和 set/map 几乎一致，只是少了有序相关的接口，新手可以直接复制运行，快速上手。

unordered_set：哈希集合，核心功能「去重、查找、判存在」

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s;

    // 1. 插入元素 (平均 O(1))
    s.insert(1);
    s.insert(2);
    s.insert(1); // 重复元素，插入失败，无报错

    // 2. 查找元素 (平均 O(1))
    if (s.find(1) != s.end()) {
        cout << "找到元素 1" << endl;
    }

    // 3. 删除元素 (平均 O(1))
    s.erase(2);

    // 4. 判空/大小/清空
    cout << "容器大小：" << s.size() << endl;
    cout << "是否为空：" << s.empty() << endl;

    // 5. 遍历（无序）
    for (auto num : s) {
        cout << num << " "; // 输出：1
    }
    return 0;
}

unordered_map：哈希映射，核心功能「键值对存储、通过 key 快速查 value」

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> mp;

    // 1. 插入键值对 (平均 O(1))
    mp["张三"] = 20;
    mp.insert({"李四", 22});
    mp.insert({"张三", 25}); // 重复 key，插入失败

    // 2. 查找 value (平均 O(1))
    if (mp.count("张三")) { // count：判断 key 是否存在，返回 0/1
        cout << "张三的年龄：" << mp["张三"] << endl; // 输出：20
    }

    // 3. 删除元素 (平均 O(1))
    mp.erase("李四");

    // 4. 遍历（无序）
    for (auto& pair : mp) {
        cout << pair.first << " : " << pair.second << endl;
    }
    return 0;
}

3. 哈希容器的高频坑点

坑点 1：哈希容器是「无序的」，遍历顺序不固定

很多新手以为哈希容器的遍历顺序和插入顺序一致，实际完全无关！遍历顺序由哈希值决定，每次运行可能都不一样，绝对不要依赖哈希容器的遍历顺序做业务逻辑。

坑点 2：自定义类型不能直接作为哈希容器的 key

比如你定义了一个 Person 结构体，直接用 unordered_set<Person> 会编译报错！原因有两个：

C++ 标准库没有为自定义类型提供默认的「哈希函数」（不知道怎么计算哈希值）；
C++ 标准库不知道怎么判断两个自定义对象是否「相等」（需要重载 == 运算符）。

坑点 3：哈希容器的迭代器失效问题

哈希容器的迭代器失效规则和 vector/list 不同

插入元素：只有当「扩容」发生时，所有迭代器失效；不扩容时，迭代器有效；
删除元素：只有被删除元素的迭代器失效，其他迭代器全部有效；

结论：哈希容器的迭代器失效问题，比 vector/list 温和得多，开发中不用过度担心。

坑点 4：哈希容器的 key 必须是「不可变的」

比如用 unordered_map<string, int>，如果修改了 key 的内容（比如 pair.first = "王五"），会导致哈希值变化，这个元素就会「丢失」，后续无法通过 key 找到。

解决方案：如果需要修改 key，先删除旧的键值对，再插入新的。

坑点 5：哈希容器不是线程安全的

C++ 标准库的所有容器（包括哈希容器）都没有实现线程安全，在多线程环境下，同时读写哈希容器会导致程序崩溃/数据错乱。

解决方案：加锁（mutex）、用线程安全的哈希容器（如 folly::ConcurrentHashMap）。

五、自定义类型作为哈希容器 key

1. 自定义类型作为哈希容器 key 的完整实现方案

需求场景：

定义一个结构体/类，比如 Student，包含学号、姓名，需要用 unordered_set<Student> 去重，或 unordered_map<Student, int> 存储成绩。

核心要求

为自定义类型 重载 == 运算符：让哈希容器能判断两个对象是否相等（解决冲突时需要）；
为自定义类型 提供哈希函数：让哈希容器能计算对象的哈希值。

完整实现代码

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

// 自定义结构体：学生
struct Student {
    int id; // 学号
    string name; // 姓名

    // 要求 1：必须重载 == 运算符，判断两个学生是否相等
    bool operator==(const Student& other) const {
        return this->id == other.id; // 学号唯一，作为相等判断依据
    }
};

// 方案 1：特化 std::hash 模板（最推荐，C++ 标准做法，面试首选）
namespace std {
    template<>
    struct hash<Student> {
        size_t operator()(const Student& s) const {
            // 计算哈希值：复用标准库对 int 的哈希函数
            return hash<int>()(s.id);
        }
    };
}

// 方案 2：自定义哈希函数，传入容器（灵活，适合临时使用）
struct StudentHash {
    size_t operator()(const Student& s) const {
        return hash<int>()(s.id);
    }
};

int main() {
    // 方案 1 使用：直接用 unordered_set
    unordered_set<Student> s1;
    s1.insert({1001, "张三"});
    s1.insert({1002, "李四"});

    // 方案 2 使用：传入自定义哈希函数
    unordered_set<Student, StudentHash> s2;
    s2.insert({1001, "张三"});

    return 0;
}

2. 多成员结构体的哈希值计算

如果结构体有多个成员（比如 id + 姓名），需要组合所有成员的哈希值，避免冲突：

size_t operator()(const Student& s) const {
    // 组合哈希值：用异或/乘质数的方式，避免单一成员冲突
    return hash<int>()(s.id) ^ (hash<string>()(s.name) << 1);
}

3. 哈希容器的性能调优技巧

提前设置初始桶数：如果知道数据量，初始化时指定 reserve(n)，避免多次扩容（扩容的 rehash 是 O(n) 操作）；比如要存 10000 个元素，直接 mp.reserve(10000)；
选择合适的哈希函数：对字符串/自定义类型，尽量用分布均匀的哈希函数，减少冲突；
避免存储大对象：哈希容器中存储指针/引用，而不是大对象，减少拷贝和内存占用；
合理调整负载因子：如果内存充足，可以手动调低负载因子，进一步降低冲突概率；

六、哈希的经典应用场景

数据去重：比如统计日志中的唯一用户 ID、去重重复的订单号，用 unordered_set 一键实现；
快速查找：比如根据用户 ID 查用户信息、根据商品编号查商品价格，用 unordered_map 实现 O(1) 查找；
频率统计：比如统计一篇文章中每个单词的出现次数、统计接口的调用次数，用 unordered_map<key, int> 计数；
缓存系统：比如 Redis 的底层就是哈希表，用哈希实现高速缓存，O(1) 查找缓存数据；
经典算法：两数之和、三数之和、四数之和的最优解都是哈希解法，时间复杂度从 O(n²) 降到 O(n)；
布隆过滤器：哈希的扩展应用，用于「快速判断元素是否存在」，比如 Redis 的缓存穿透防护。

一、哈希的核心概念

1. 哈希到底是什么？

先回忆两个基础数据结构的痛点：

数组：支持下标 O(1) 查找，但只能通过「连续数字下标」访问，无法通过「任意数据（如字符串、自定义对象）」快速查找；
链表：支持任意数据存储，但查找/删除需要从头遍历，时间复杂度 O(n)，数据量越大越慢。

哈希的核心解决思路：

最终效果：查找/插入/删除的平均时间复杂度都是 O(1)，和数据量无关，极致高效！

2. 哈希的核心基础概念

概念 1：哈希函数 (Hash Function)

定义：把任意输入值（key）映射成固定范围整型值（哈希值）的函数，记为 hash(key) = value。

核心要求

确定性：同一个 key，永远得到同一个哈希值（绝对不能同一个 key，这次算出来是 5，下次是 8）；
高效性：计算哈希值的速度要快，不能比查找本身还耗时；
均匀性：尽量让不同的 key 映射到不同的哈希值，减少冲突。

C++ 中常见的哈希函数

取模法：hash(key) = key % 数组长度（最基础，比如学号 1001，模 10 得到哈希值 1）；
直接定址法：hash(key) = key（比如 key 是整型 ID，直接用 ID 当下标）；
字符串哈希：将字符串的每个字符转成数字，通过加权求和得到哈希值（C++ 标准库对 string 的哈希就是这种实现）。

概念 2：哈希表 (Hash Table)

定义：哈希的底层存储结构，本质是「数组 + 冲突解决结构」。

我们把哈希函数计算出的哈希值，作为数组的「下标」，这个数组的每个位置称为「桶（bucket）」，数据就存在对应的桶里。

如果没有哈希冲突，哈希表就是一个简单的数组，所有操作都是 O(1)。

概念 3：哈希冲突 (Hash Collision)

1. 什么是哈希冲突？

白话解释：不同的原始 key，通过哈希函数计算后，得到了相同的哈希值，最终要存在哈希表的同一个桶里，这种情况就是哈希冲突。

比如：哈希函数是 hash(key) = key % 10，那么 key=1 和 key=11，计算出的哈希值都是 1，就会发生冲突。

哈希冲突是无法避免的，只能尽可能减少和解决。

原因：哈希函数是「将无限大的输入值域」映射到「有限小的哈希值范围」，就像把 1000 个苹果放进 100 个篮子，必然有篮子放多个苹果。

二、哈希冲突的核心解决方法

方法 1：拉链法 (Separate Chaining)

1. 拉链法的本质：给哈希表的每个桶挂个'链条'

拉链法是解决哈希冲突的最主流、最易实现的方案，没有之一。

它的核心思路是：

哈希表的底层是一个数组，数组的每个元素称为一个 桶（Bucket）；
每个桶不再只存一个数据，而是指向一个 链表/红黑树 的表头；
当不同的 key 计算出相同的哈希值（发生冲突）时，不会争抢同一个桶的位置，而是像挂灯笼一样，把新数据挂载到对应桶的'链条'末尾。

形象比喻：把哈希表的数组想象成一排挂钩，每个挂钩就是一个桶；冲突的数据就是一串钥匙，全挂在同一个挂钩上，互不干扰。

2. 拉链法的核心结构

哈希表数组（桶数组）
索引 0 → 桶 0 → 链表节点 (key:A, val:1) → 链表节点 (key:J, val:3) → null
索引 1 → 桶 1 → 链表节点 (key:B, val:2) → null
索引 2 → 桶 2 → null （空桶）
索引 3 → 桶 3 → 链表节点 (key:D, val:5) → 链表节点 (key:M, val:7) → 链表节点 (key:X, val:9) → null

桶数组：承载哈希值的索引，决定了哈希表的基础容量；
链条结构：早期是单向链表，C++11 后优化为 '链表 + 红黑树' 混合结构；
节点：存储 key、value 和指向下一个节点的指针。

3. 为什么 C++ 标准库选拉链法？

对比开放寻址法，拉链法的优势是工程上的'容错性'和'易用性'，这也是标准库选择它的核心原因：

特性	拉链法	开放寻址法
冲突处理难度	简单（挂链表即可）	复杂（需找空位，处理删除）
负载因子容忍度	高（>1 也能工作）	低（>0.7 性能急剧下降）
内存利用率	非连续内存，灵活分配	连续数组，易浪费空间
删除操作	直接删链表节点，无残留	需'标记删除'，易产生空洞
扩容成本	元素迁移时不影响原链条	需重新探测所有元素位置

结论：拉链法更适合作为通用哈希容器的冲突解决方案，开放寻址法仅适合内存极度紧张的嵌入式场景。

4. 拉链法的核心操作：插入、查找、删除

插入操作

输入：key 和 value

核心目标：将数据挂载到对应桶的链条上，且保证 key 唯一

步骤拆解：

计算哈希值：通过哈希函数 hash(key) 得到哈希值 h；
计算桶索引：通过取模运算得到桶的下标 index = h % 桶数组长度（取模是最基础的映射方式）；
检查冲突：遍历桶 index 对应的链表：
- 如果找到相同的 key：更新 value，结束插入；
- 如果遍历到链表末尾都没找到相同 key：执行下一步；
挂载新节点：创建新的链表节点，将节点插入到链表头部或尾部（头部插入效率更高，无需遍历到末尾）；
检查负载因子：如果 元素总数 / 桶数组长度 > 负载因子阈值（默认 0.75），触发扩容（桶数组长度翻倍，所有元素重新哈希迁移）。

头部插入 vs 尾部插入

头部插入：时间 O(1)，无需遍历链表，是工程上的首选；
尾部插入：时间 O(k)，需要遍历到链表末尾，仅在需要保持插入顺序时使用（C++ 标准库不保证顺序，所以用头部插入）。

查找操作（平均 O(1)，最坏 O(k)）

输入：要查找的 key

核心目标：找到对应桶的链条中 key 匹配的节点

步骤拆解：

计算哈希值 h 和桶索引 index（同插入步骤 1-2）；
遍历桶 index 对应的链表：
- 如果找到 key 匹配的节点：返回 value，查找成功；
- 如果遍历到链表末尾未找到：返回'不存在'，查找失败。

性能瓶颈：当链条长度 k 过大时，查找效率会从 O(1) 退化到 O(k)—— 这也是 C++ 标准库引入红黑树优化的原因。

删除操作（平均 O(1)，最坏 O(k)）

输入：要删除的 key

核心目标：从链条中移除 key 匹配的节点，保证链表结构不断裂

步骤拆解：

计算哈希值 h 和桶索引 index（同插入步骤 1-2）；
遍历桶 index 对应的链表，同时记录当前节点和前驱节点：
- 如果找到 key 匹配的节点：
  - 如果是头节点：让桶直接指向头节点的下一个节点；
  - 如果是中间/尾节点：让前驱节点的指针指向当前节点的下一个节点；
  - 释放当前节点的内存，删除成功；
- 如果遍历到链表末尾未找到：删除失败。

关键细节：必须记录前驱节点，否则删除中间节点后，链表会断裂，后续节点会'丢失'。

5. C++ 标准库的拉链法优化：链表→红黑树

为什么要做这个优化？

链表的痛点：当链条长度 k=8 时，最坏查找时间是 O(8)；当 k=100 时，退化到 O(100)，性能极差；
红黑树的优势：红黑树是平衡二叉树，最坏查找时间是 O(log k)，当 k=8 时，O(log 8)=O(3)，比链表快 2 倍多；当 k=100 时，O(log 100)≈O(7)，比链表快 14 倍。

阈值选择的原因

转红黑树阈值 = 8：经过大量实验，当链表长度超过 8 时，红黑树的 O(log k) 优势开始超过链表；
转链表阈值 = 6：设置一个'回退阈值'，避免长度在 8 附近波动时，频繁在链表和红黑树之间切换（比如长度从 8→7→8，反复转换会消耗大量性能）。

结论：这个优化让 C++ 的哈希容器，在极端冲突场景下，依然能保持高效的查找性能。

6. 手写拉链法哈希表

#include <iostream>
#include <string>
using namespace std;

// 定义链表节点结构
template <typename K, typename V>
struct HashNode {
    K key; // 键
    V value; // 值
    HashNode<K, V>* next; // 指向下一个节点的指针

    // 构造函数
    HashNode(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
};

// 简易拉链法哈希表
template <typename K, typename V>
class HashTable {
private:
    using Node = HashNode<K, V>;
    Node** buckets; // 桶数组：二级指针，指向指针数组
    size_t bucketCount; // 桶的数量
    size_t elementCount; // 元素总数
    const float loadFactorThreshold = 0.75f; // 负载因子阈值

    // 简易哈希函数：针对 string 类型（可扩展其他类型）
    size_t hashFunc(const string& key) const {
        size_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c; // 31 是质数，减少哈希冲突
        }
        return hash;
    }

    // 针对 int 类型的哈希函数
    size_t hashFunc(int key) const {
        return key;
    }

    // 计算桶索引
    size_t getBucketIndex(const K& key) const {
        return hashFunc(key) % bucketCount;
    }

    // 扩容：桶数量翻倍，所有元素重新哈希
    void resize() {
        size_t newBucketCount = bucketCount * 2;
        Node** newBuckets = new Node*[newBucketCount](); // 初始化所有桶为 nullptr

        // 遍历旧桶，将所有元素迁移到新桶
        for (size_t i = 0; i < bucketCount; ++i) {
            Node* curr = buckets[i];
            while (curr != nullptr) {
                Node* next = curr->next; // 保存下一个节点，避免迁移时丢失
                // 计算新桶索引
                size_t newIndex = hashFunc(curr->key) % newBucketCount;
                // 头部插入新桶
                curr->next = newBuckets[newIndex];
                newBuckets[newIndex] = curr;
                curr = next;
            }
            delete[] buckets[i]; // 释放旧桶的链表节点
        }

        // 替换桶数组
        delete[] buckets;
        buckets = newBuckets;
        bucketCount = newBucketCount;
    }

public:
    // 构造函数：初始化桶数组
    HashTable(size_t initBucketCount = 16) : bucketCount(initBucketCount), elementCount(0) {
        // 初始化桶数组，每个桶初始为 nullptr
        buckets = new Node*[bucketCount]();
    }

    // 析构函数：释放所有内存
    ~HashTable() {
        for (size_t i = 0; i < bucketCount; ++i) {
            Node* curr = buckets[i];
            while (curr != nullptr) {
                Node* next = curr->next;
                delete curr;
                curr = next;
            }
        }
        delete[] buckets;
    }

    // 插入/更新元素
    void put(const K& key, const V& value) {
        // 检查负载因子，触发扩容
        if (static_cast<float>(elementCount) / bucketCount > loadFactorThreshold) {
            resize();
        }
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];

        // 遍历链表，检查 key 是否存在
        while (curr != nullptr) {
            if (curr->key == key) {
                curr->value = value; // key 存在，更新 value
                return;
            }
            curr = curr->next;
        }

        // key 不存在，头部插入新节点
        Node* newNode = new Node(key, value);
        newNode->next = buckets[index];
        buckets[index] = newNode;
        elementCount++;
    }

    // 查找元素
    bool get(const K& key, V& value) {
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];
        while (curr != nullptr) {
            if (curr->key == key) {
                value = curr->value; // 找到 key，返回 value
                return true;
            }
            curr = curr->next;
        }
        return false; // key 不存在
    }

    // 删除元素
    bool remove(const K& key) {
        size_t index = getBucketIndex(key);
        Node* curr = buckets[index];
        Node* prev = nullptr; // 记录前驱节点

        while (curr != nullptr) {
            if (curr->key == key) {
                // 处理删除逻辑
                if (prev == nullptr) { // 删除头节点
                    buckets[index] = curr->next;
                } else { // 删除中间/尾节点
                    prev->next = curr->next;
                }
                delete curr;
                elementCount--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false; // key 不存在
    }

    // 获取元素总数
    size_t size() const {
        return elementCount;
    }
};

// 测试代码
int main() {
    HashTable<string, int> ht;

    // 插入元素
    ht.put("apple", 5);
    ht.put("banana", 3);
    ht.put("apple", 10); // 更新 apple 的值

    // 查找元素
    int value;
    if (ht.get("apple", value)) {
        cout << "apple: " << value << endl; // 输出 10
    }

    // 删除元素
    ht.remove("banana");
    cout << "size: " << ht.size() << endl; // 输出 1

    return 0;
}

代码核心亮点

模板化设计：支持任意 key/value 类型，通用性强；
手动扩容逻辑：严格遵循负载因子阈值，体现哈希表的核心优化思想；
头部插入策略：保证插入操作的 O(1) 时间复杂度；
内存安全：析构函数释放所有节点和桶数组，避免内存泄漏。

7. 拉链法的工程优化技巧

在实际项目中，使用拉链法哈希表（比如 unordered_map）时，掌握这些技巧能大幅提升性能：

提前 reserve 容量：如果知道数据量，初始化时调用 reserve(n)，避免多次扩容（扩容的 rehash 操作是 O(n)，很耗时）；

unordered_map<string, int> mp;
mp.reserve(10000); // 提前分配足够的桶，避免插入 10000 个元素时多次扩容

自定义高效哈希函数：标准库的 string 哈希函数在极端场景下冲突率较高，可以自定义哈希函数（比如结合 BKDRHash 等工业级哈希算法）；
避免存储大对象：在桶的链条中存储指针/引用，而非大对象，减少拷贝和内存占用；
合理设置负载因子：如果内存充足，可以手动调低负载因子（比如 0.5），进一步降低冲突概率（需通过自定义哈希表实现，标准库不支持修改）。

方法 2：开放寻址法 (Open Addressing)

原理

简单理解：一个桶被占了，就去隔壁桶看看，直到找到空桶。

核心优缺点

适用场景：内存紧张的嵌入式开发、高性能缓存系统，C++ 中极少用标准库实现，一般是手写。

三、哈希的核心性能指标 + 特性

1. 哈希的核心性能指标：负载因子 (Load Factor)

定义

负载因子 α = 哈希表中存储的元素个数 / 哈希表的桶的总数。比如：哈希表有 100 个桶，存了 75 个元素，负载因子就是 0.75。

核心作用

负载因子是衡量哈希表拥挤程度的核心指标，也是哈希表「扩容」的唯一触发条件！

α 越小：桶的数量远大于元素数，冲突概率极低，性能接近纯数组的 O(1)，但空间利用率低；
α 越大：桶的数量接近元素数，冲突概率急剧上升，性能退化严重，空间利用率高；

为什么 C++ 的哈希容器默认负载因子是 0.75？

2. 哈希的核心时间复杂度

哈希表的 平均时间复杂度：查找、插入、删除都是 O(1)；

哈希表的 最坏时间复杂度：查找、插入、删除都是 O(n)；

最坏情况的触发原因：

哈希函数设计极差，所有 key 都映射到同一个哈希值，拉链法变成单链表；
恶意构造数据，让所有 key 都冲突；
负载因子过高，没有及时扩容。

3. 哈希的核心特性

无序性：哈希表的元素存储顺序和插入顺序无关，也和 key 的大小无关，因为元素的位置由哈希值决定。这是 C++ 中 unordered_* 容器和 set/map 的核心区别之一；
键的唯一性：哈希集合（unordered_set）中，同一个 key 只能存一次；哈希映射（unordered_map）中，key 是唯一的，value 可以重复；
键的不可变性：哈希容器的 key绝对不能被修改！因为 key 的哈希值是初始化时计算的，修改 key 会导致哈希值变化，元素就会「丢失」在哈希表中，无法被找到。

四、哈希容器的使用

C++ 对哈希的支持是从 C++11 开始的，提供了两个核心的哈希容器，也是项目开发中最常用的容器，没有之一。

1. C++ 哈希容器全家福：unordered_set & unordered_map

核心结论

C++ 的 unordered_set 和 unordered_map：

底层都是哈希表，采用「拉链法」解决哈希冲突；
所有操作的平均时间复杂度 O(1)，最坏 O(n)；
容器内的元素是无序的；
依赖 C++11 及以上标准，项目中必须开启 -std=c++11 编译。

哈希容器 vs 有序容器（set/map）：怎么选？

特性	unordered_set/unordered_map（哈希）	set/map（红黑树）
底层实现	哈希表 + 拉链法	红黑树（平衡二叉树）
元素顺序	无序	按键升序排列
平均时间复杂度	O(1) 极致高效	O(log n) 稳定高效
最坏时间复杂度	O(n)	O(log n) 永远稳定
内存占用	较大（空间换时间）	较小
适用场景	只需要查找/插入/删除，不需要有序	需要有序遍历、范围查询

能哈希，不树型；要有序，再树型。

简单说：只要业务不需要有序，优先用哈希容器，性能碾压红黑树容器！

2. 哈希容器的基础用法

语法极简，和 set/map 几乎一致，只是少了有序相关的接口，新手可以直接复制运行，快速上手。

unordered_set：哈希集合，核心功能「去重、查找、判存在」

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s;

    // 1. 插入元素 (平均 O(1))
    s.insert(1);
    s.insert(2);
    s.insert(1); // 重复元素，插入失败，无报错

    // 2. 查找元素 (平均 O(1))
    if (s.find(1) != s.end()) {
        cout << "找到元素 1" << endl;
    }

    // 3. 删除元素 (平均 O(1))
    s.erase(2);

    // 4. 判空/大小/清空
    cout << "容器大小：" << s.size() << endl;
    cout << "是否为空：" << s.empty() << endl;

    // 5. 遍历（无序）
    for (auto num : s) {
        cout << num << " "; // 输出：1
    }
    return 0;
}

unordered_map：哈希映射，核心功能「键值对存储、通过 key 快速查 value」

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> mp;

    // 1. 插入键值对 (平均 O(1))
    mp["张三"] = 20;
    mp.insert({"李四", 22});
    mp.insert({"张三", 25}); // 重复 key，插入失败

    // 2. 查找 value (平均 O(1))
    if (mp.count("张三")) { // count：判断 key 是否存在，返回 0/1
        cout << "张三的年龄：" << mp["张三"] << endl; // 输出：20
    }

    // 3. 删除元素 (平均 O(1))
    mp.erase("李四");

    // 4. 遍历（无序）
    for (auto& pair : mp) {
        cout << pair.first << " : " << pair.second << endl;
    }
    return 0;
}

3. 哈希容器的高频坑点

坑点 1：哈希容器是「无序的」，遍历顺序不固定

坑点 2：自定义类型不能直接作为哈希容器的 key

比如你定义了一个 Person 结构体，直接用 unordered_set<Person> 会编译报错！原因有两个：

C++ 标准库没有为自定义类型提供默认的「哈希函数」（不知道怎么计算哈希值）；
C++ 标准库不知道怎么判断两个自定义对象是否「相等」（需要重载 == 运算符）。

坑点 3：哈希容器的迭代器失效问题

哈希容器的迭代器失效规则和 vector/list 不同

插入元素：只有当「扩容」发生时，所有迭代器失效；不扩容时，迭代器有效；
删除元素：只有被删除元素的迭代器失效，其他迭代器全部有效；

结论：哈希容器的迭代器失效问题，比 vector/list 温和得多，开发中不用过度担心。

坑点 4：哈希容器的 key 必须是「不可变的」

解决方案：如果需要修改 key，先删除旧的键值对，再插入新的。

坑点 5：哈希容器不是线程安全的

C++ 标准库的所有容器（包括哈希容器）都没有实现线程安全，在多线程环境下，同时读写哈希容器会导致程序崩溃/数据错乱。

解决方案：加锁（mutex）、用线程安全的哈希容器（如 folly::ConcurrentHashMap）。

五、自定义类型作为哈希容器 key

1. 自定义类型作为哈希容器 key 的完整实现方案

需求场景：

定义一个结构体/类，比如 Student，包含学号、姓名，需要用 unordered_set<Student> 去重，或 unordered_map<Student, int> 存储成绩。

核心要求

为自定义类型 重载 == 运算符：让哈希容器能判断两个对象是否相等（解决冲突时需要）；
为自定义类型 提供哈希函数：让哈希容器能计算对象的哈希值。

完整实现代码

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

// 自定义结构体：学生
struct Student {
    int id; // 学号
    string name; // 姓名

    // 要求 1：必须重载 == 运算符，判断两个学生是否相等
    bool operator==(const Student& other) const {
        return this->id == other.id; // 学号唯一，作为相等判断依据
    }
};

// 方案 1：特化 std::hash 模板（最推荐，C++ 标准做法，面试首选）
namespace std {
    template<>
    struct hash<Student> {
        size_t operator()(const Student& s) const {
            // 计算哈希值：复用标准库对 int 的哈希函数
            return hash<int>()(s.id);
        }
    };
}

// 方案 2：自定义哈希函数，传入容器（灵活，适合临时使用）
struct StudentHash {
    size_t operator()(const Student& s) const {
        return hash<int>()(s.id);
    }
};

int main() {
    // 方案 1 使用：直接用 unordered_set
    unordered_set<Student> s1;
    s1.insert({1001, "张三"});
    s1.insert({1002, "李四"});

    // 方案 2 使用：传入自定义哈希函数
    unordered_set<Student, StudentHash> s2;
    s2.insert({1001, "张三"});

    return 0;
}

2. 多成员结构体的哈希值计算

如果结构体有多个成员（比如 id + 姓名），需要组合所有成员的哈希值，避免冲突：

size_t operator()(const Student& s) const {
    // 组合哈希值：用异或/乘质数的方式，避免单一成员冲突
    return hash<int>()(s.id) ^ (hash<string>()(s.name) << 1);
}

3. 哈希容器的性能调优技巧

提前设置初始桶数：如果知道数据量，初始化时指定 reserve(n)，避免多次扩容（扩容的 rehash 是 O(n) 操作）；比如要存 10000 个元素，直接 mp.reserve(10000)；
选择合适的哈希函数：对字符串/自定义类型，尽量用分布均匀的哈希函数，减少冲突；
避免存储大对象：哈希容器中存储指针/引用，而不是大对象，减少拷贝和内存占用；
合理调整负载因子：如果内存充足，可以手动调低负载因子，进一步降低冲突概率；

六、哈希的经典应用场景

数据去重：比如统计日志中的唯一用户 ID、去重重复的订单号，用 unordered_set 一键实现；
快速查找：比如根据用户 ID 查用户信息、根据商品编号查商品价格，用 unordered_map 实现 O(1) 查找；
频率统计：比如统计一篇文章中每个单词的出现次数、统计接口的调用次数，用 unordered_map<key, int> 计数；
缓存系统：比如 Redis 的底层就是哈希表，用哈希实现高速缓存，O(1) 查找缓存数据；
经典算法：两数之和、三数之和、四数之和的最优解都是哈希解法，时间复杂度从 O(n²) 降到 O(n)；
布隆过滤器：哈希的扩展应用，用于「快速判断元素是否存在」，比如 Redis 的缓存穿透防护。

哈希（Hash）核心概念与 C++ 应用

一、哈希的核心概念

1. 哈希到底是什么？

2. 哈希的核心基础概念

二、哈希冲突的核心解决方法

方法 1：拉链法 (Separate Chaining)

方法 2：开放寻址法 (Open Addressing)

三、哈希的核心性能指标 + 特性

1. 哈希的核心性能指标：负载因子 (Load Factor)

2. 哈希的核心时间复杂度

3. 哈希的核心特性

四、哈希容器的使用

1. C++ 哈希容器全家福：unordered_set & unordered_map

2. 哈希容器的基础用法

3. 哈希容器的高频坑点

五、自定义类型作为哈希容器 key

1. 自定义类型作为哈希容器 key 的完整实现方案

2. 多成员结构体的哈希值计算

3. 哈希容器的性能调优技巧

六、哈希的经典应用场景

哈希（Hash）核心概念与 C++ 应用

一、哈希的核心概念

1. 哈希到底是什么？

2. 哈希的核心基础概念

二、哈希冲突的核心解决方法

方法 1：拉链法 (Separate Chaining)

方法 2：开放寻址法 (Open Addressing)

三、哈希的核心性能指标 + 特性

1. 哈希的核心性能指标：负载因子 (Load Factor)

2. 哈希的核心时间复杂度

3. 哈希的核心特性

四、哈希容器的使用

1. C++ 哈希容器全家福：unordered_set & unordered_map

2. 哈希容器的基础用法

3. 哈希容器的高频坑点

五、自定义类型作为哈希容器 key

1. 自定义类型作为哈希容器 key 的完整实现方案

2. 多成员结构体的哈希值计算

3. 哈希容器的性能调优技巧

六、哈希的经典应用场景

更多推荐文章

相关免费在线工具

更多推荐文章

相关免费在线工具