哈希表是笔试刷题和工程开发里都非常高频的一种数据结构。很多刚接触它的人会觉得它有点“玄学”：为什么查找可以很快，为什么有时候又会退化，为什么 C++ 里 unordered_map 看起来很方便，但底层又好像并不简单。实际上，哈希表并不神秘，它的核心思路非常朴素，本质上就是想办法把“原本可能需要遍历的数据查找”，转化为“尽量直接定位到某个位置的查找”。

这篇文章不打算一上来就陷入复杂的底层细节，而是按照一个更自然的顺序展开：先把哈希表的基本概念建立起来，再用 C++ 手写一个最小可运行版本，接着介绍 C++ 标准库里的哈希容器，最后结合实际例子看它和暴力、数组、链表方案之间到底差在哪里。这样学下来，既能理解原理，也能直接上手做题。

---

1. 哈希表介绍

1.1 哈希表是什么

哈希表，英文叫 Hash Table，本质上是一种用于快速查找的数据结构。

理解哈希表时，可以先把它想成一个“更聪明的数组”。普通数组的使用方式很直接，例如：

arr[3] = 100;

这里的下标 3 是我们事先就知道并直接给出的，因此数组按下标访问的速度非常快，时间复杂度通常可以看作 O(1)。但问题在于，现实中的很多查找问题并不是“已知下标去访问数据”，而是“已知某个值，想快速判断它是否存在，或者想找到它对应的信息”。

例如，我们可能需要处理下面这些 key：

• 一个数字 42
• 一个字符串 "apple"
• 一个学号 "20260001"
• 一个坐标对 (x, y)

这些值都不能直接作为数组下标使用。于是就需要一个函数，把这些“key”转化为一个整数位置，这个过程就叫哈希或散列；对应的函数叫哈希函数；计算出来的结果叫哈希值。

因此，哈希表可以粗略地理解为：

先用哈希函数把 key 转换成一个数组下标，再到数组对应的位置中存储或查找数据。

这就是哈希表最核心的思想。它并没有摆脱数组，而是在数组的基础上加入了一层“映射”，从而把原本不方便直接定位的数据，尽量变成可以快速定位的数据。

从更实际的角度看，哈希表解决的核心问题是：如何把原本可能需要线性遍历的查找，尽量优化成接近常数时间的查找。
这也是它在算法题和工程开发中如此高频的根本原因。

---

1.2 哈希表解决了什么问题，与数组和链表有什么区别

如果没有哈希表，最常见的数据存储方式通常是数组和链表。但这两种结构虽然都很基础，却各有明显局限。

对于数组来说，它最大的优点是按下标访问非常快。只要知道位置，就能立刻取到元素，这一点几乎是所有基础数据结构里最直接、最高效的。但是数组更擅长的是“按位置访问”，而不是“按值查找”。如果只给你一个值，而不知道它在数组中的位置，那么通常只能从头到尾依次比较，这样的查找本质上仍然是线性查找，时间复杂度通常为 O(n)。

链表则是另一种典型结构。它的优点是插入和删除更灵活，不需要像数组那样频繁搬移元素。但链表的查找问题更明显：由于链表中的元素在内存中并不连续，只能顺着指针一个一个往后找，因此查找某个值时通常也只能线性遍历，时间复杂度同样是 O(n)。

也就是说：

• 数组：适合按下标快速访问，不擅长按值查找。
• 链表：适合频繁插入删除，但查找仍然很慢。
• 哈希表：重点解决“按值快速查找”的问题。

哈希表的思路和数组、链表都不同。它并不是直接去遍历所有数据，而是先通过哈希函数，把 key 映射到某个较小的局部范围，再在这个局部范围内完成查找。换句话说，哈希表追求的不是“彻底不查找”，而是尽量避免全局遍历，把查找缩小到一个很小的局部中去完成。

所以，从使用体验上看，哈希表更像是：

• 借用了数组的“定位快”这一优点；
• 同时又借助链表等结构来处理同一个位置上的多个元素。

这也是为什么说，哈希表本质上不是一种完全脱离数组的新结构，而是数组思想的一种扩展和增强。

---

1.3 哈希表是如何实现的，什么是哈希冲突

哈希表之所以能够提高查找效率，关键就在于哈希函数。

哈希函数的作用，是把一个 key 转换成表中的某个位置。例如，对整数而言，一个最简单的哈希函数可以写成：

index = key % capacity;

其中 capacity 表示哈希表当前的容量，也就是桶的数量。如果哈希表容量为 8，那么对于几个不同的 key，有：

1 % 8  = 1
9 % 8  = 1
17 % 8 = 1
2 % 8  = 2

这意味着 key 为 1、9、17 的元素都会被映射到编号为 1 的桶中，而 key 为 2 的元素会被映射到编号为 2 的桶中。查找某个 key 时，只需要重新计算一次哈希值，就可以直接定位到它“应该出现”的桶，再在这个桶中继续查找。这比从整个数组或链表里逐个比较，范围已经小得多了。

不过，这里会立刻出现一个不可避免的问题：不同的 key 可能会被映射到同一个位置。

例如在上面的例子中，1、9、17 都被映射到了桶 1。这种现象就叫哈希冲突。

很多初学者会误以为，哈希表的理想状态是“没有冲突”。实际上这几乎不可能。因为 key 的取值空间往往很大，而哈希表的容量总是有限的，只要把大量不同的 key 压缩映射到有限个桶中，冲突就几乎一定会发生。换句话说，哈希冲突不是设计失败，而是哈希表必须面对的常态。

既然冲突不可避免，那么真正关键的问题就变成了：冲突发生以后怎么处理。

最常见的一种方法是拉链法，也叫链地址法。它的基本思路是：哈希表底层仍然是一个数组，但数组的每个位置不只存一个元素，而是存一个链表的头指针。所有映射到同一个桶的元素，都挂到同一条链表上。

例如：

bucket[1] -> (1, value1) -> (9, value2) -> (17, value3)

这样，当我们查找 key 为 9 的元素时，并不需要扫描整个表，而只需要：

1. 先计算哈希值，定位到 bucket[1]
2. 再在 bucket[1] 这条链表中顺序比较

由此可见，哈希表并不是完全不遍历，而是只遍历一个局部桶中的少量元素。只要哈希函数设计得比较合理，元素分布比较均匀，那么每个桶中的元素数量通常不会太多，查找效率就会很高。

除了拉链法之外，哈希冲突还有另一类常见处理思路，叫开放寻址法。它的做法不是在桶中挂链表，而是当某个位置被占用时，继续向后寻找其他可用位置。开放寻址法在实现方式和性能特征上与拉链法不同，但本质上也是为了解决“多个 key 落到同一个位置”的问题。本文后续的示例实现会采用更直观的拉链法，因为它更容易理解，也更适合初学阶段建立直觉。

---

1.4 负载因子与时间复杂度

理解哈希表时，另一个非常重要的概念是负载因子。

它通常定义为：

负载因子 = 元素个数 / 桶个数

例如，一个哈希表有 10 个桶，当前存了 7 个元素，那么它的负载因子就是：

0.7

负载因子的含义并不复杂，它本质上反映了哈希表“装得有多满”。负载因子越大，说明每个桶里平均分到的元素越多，发生冲突的概率通常也越高，桶内链表或探测路径就会变长，查找效率自然会下降。

因此，真正的哈希表实现不会无限制地往一个固定大小的表中塞数据，而是在负载因子达到某个阈值之后进行扩容。扩容不是简单地把底层数组开大一点就结束了，因为哈希函数通常依赖容量，比如 % capacity，容量一变，所有元素原本对应的桶位置也会发生变化。所以扩容之后，通常还需要把原有元素重新计算哈希值并重新放入新表中，这个过程叫重新哈希，也就是 rehash。

基于这些机制，哈希表的时间复杂度通常这样描述：

• 平均时间复杂度：O(1)
• 最坏时间复杂度：O(n)

这里必须特别强调，“哈希表查找是 O(1)”这句话只在平均意义上成立。之所以平均能达到 O(1)，是因为查找过程通常只需要两步：先通过哈希函数定位桶，然后在桶内查找少量元素。如果哈希函数设计合理、数据分布比较均匀、负载因子控制得当，那么每个桶里元素数量通常都比较少，整个查找过程就可以近似看作常数时间。

但在最坏情况下，情况会完全不同。比如：

• 如果使用拉链法，而大量元素都哈希到了同一个桶中，那么这个桶上的链表会变得很长，查找就会退化成链表遍历；
• 如果使用开放寻址法，而冲突非常严重，那么查找时就可能需要进行长距离探测，性能同样会显著下降。

在这种情况下，哈希表的查找、插入、删除都可能退化到 O(n)。

因此，更严谨的说法应该是：

哈希表并不是“永远 O(1)”，而是在哈希函数合理、冲突分布可控、负载因子不过高的前提下，平均性能可以达到 O(1)。

这也是哈希表在工程实践中需要关注哈希函数设计、桶数量选择以及扩容策略的原因。

---

2. 用 C++ 实现一个最小哈希表

在理解了哈希表的基本思想之后，最好的下一步不是马上去背 unordered_map 的各种接口，而是自己动手写一个最小可运行版本。因为只有真正把“桶”“哈希函数”“冲突处理”“插入查找”这些概念落到代码里，哈希表才不再只是一个抽象名词。

这里实现一个最简单的哈希表，目标不追求工业级完整性，而是先把核心机制说明白。这个版本支持以下几个基本能力：插入键值对、查找某个 key 对应的 value、如果 key 已存在则更新 value、最后打印整个哈希表结构。冲突处理方式采用上一章提到的拉链法，也就是“数组 + 链表”的结构。

2.1 最小可运行代码

#include <iostream>
#include <vector>

using namespace std;

class HashTable {
private:
    struct Node {
        int key;
        int value;
        Node* next;

        Node(int k, int v) : key(k), value(v), next(nullptr) {}
    };

    vector<Node*> buckets;
    int capacity;

    int hash(int key) const {
        if (key < 0) {
            key = -key;
        }
        return key % capacity;
    }

public:
    HashTable(int cap = 8) : capacity(cap), buckets(cap, nullptr) {}

    ~HashTable() {
        for (int i = 0; i < capacity; i++) {
            Node* cur = buckets[i];
            while (cur != nullptr) {
                Node* next = cur->next;
                delete cur;
                cur = next;
            }
        }
    }

    void put(int key, int value) {
        int index = hash(key);
        Node* cur = buckets[index];

        while (cur != nullptr) {
            if (cur->key == key) {
                cur->value = value;
                return;
            }
            cur = cur->next;
        }

        Node* newNode = new Node(key, value);
        newNode->next = buckets[index];
        buckets[index] = newNode;
    }

    bool get(int key, int& outValue) const {
        int index = hash(key);
        Node* cur = buckets[index];

        while (cur != nullptr) {
            if (cur->key == key) {
                outValue = cur->value;
                return true;
            }
            cur = cur->next;
        }

        return false;
    }

    void print() const {
        for (int i = 0; i < capacity; i++) {
            cout << "bucket[" << i << "]: ";
            Node* cur = buckets[i];
            while (cur != nullptr) {
                cout << "(" << cur->key << " -> " << cur->value << ") ";
                cur = cur->next;
            }
            cout << endl;
        }
    }
};

int main() {
    HashTable ht(8);

    ht.put(1, 100);
    ht.put(9, 900);
    ht.put(17, 1700);
    ht.put(2, 200);

    cout << "当前哈希表内容：" << endl;
    ht.print();

    int value;

    if (ht.get(9, value)) {
        cout << "找到 key=9, value=" << value << endl;
    } else {
        cout << "没有找到 key=9" << endl;
    }

    if (ht.get(3, value)) {
        cout << "找到 key=3, value=" << value << endl;
    } else {
        cout << "没有找到 key=3" << endl;
    }

    ht.put(9, 9999);
    if (ht.get(9, value)) {
        cout << "更新后 key=9, value=" << value << endl;
    }

    return 0;
}

这段代码已经具备了一个最小哈希表应该有的核心行为。虽然它还没有实现删除、扩容、重哈希等更完整的功能，但从“学习原理”的角度来说，已经足够把哈希表最关键的结构展示出来。

2.2 代码整体结构分析

这份实现的底层结构非常简单，本质上就是一个桶数组，数组中的每个元素都是一个链表头指针。代码里对应的是这一句：

vector<Node*> buckets;

它其实就相当于“一个指针数组”，哈希表底层依然离不开数组，只不过数组中的每个位置不再直接存单个值，而是挂着一条链表，用来处理哈希冲突。

链表节点由 Node 结构体表示：

struct Node {
    int key;
    int value;
    Node* next;

    Node(int k, int v) : key(k), value(v), next(nullptr) {}
};

这里每个节点保存三部分信息：key、value 和指向下一个节点的指针 next。

整个哈希表最重要的成员还有一个 capacity，表示当前桶的数量。桶的数量决定了哈希函数映射出的范围，也直接影响冲突概率。桶越少，冲突通常越容易发生；桶越多，冲突会缓解，但空间占用也会更大。

哈希函数本身写得非常简单：

int hash(int key) const {
    if (key < 0) {
        key = -key;
    }
    return key % capacity;
}

这里使用最朴素的 % capacity 方式，把整数 key 映射到 0 ~ capacity-1 的范围内。这个写法不复杂，但足以说明哈希表的工作方式。需要注意的是，这里先对负数取绝对值，是为了避免出现负下标。

2.3 插入、查找与冲突处理过程

哈希表最核心的两个操作就是插入和查找。只要把这两个过程理解透了，哈希表的整体逻辑就基本清楚了。

先看插入操作 put()。它的第一步不是直接遍历数据，而是先计算当前 key 应该落到哪个桶：

int index = hash(key);

拿 capacity = 8 举例：

1 % 8  = 1
9 % 8  = 1
17 % 8 = 1
2 % 8  = 2

这意味着 key 为 1、9、17 的元素都会落入 bucket[1]，而 key 为 2 的元素会落入 bucket[2]。也就是说，插入过程本质上先完成了“全局定位”，再在局部桶中处理细节。

接下来，put() 会先遍历当前桶上的链表，检查这个 key 是否已经存在：

while (cur != nullptr) {
    if (cur->key == key) {
        cur->value = value;
        return;
    }
    cur = cur->next;
}

如果 key 已经存在，就直接更新它的 value，然后返回。这说明哈希表中的 key 是唯一的，重复插入同一个 key 的结果不是增加一个新节点，而是覆盖旧值。

如果当前桶中没有这个 key，就说明这是一个新的键值对。此时就创建一个新节点，并采用头插法挂到当前桶的链表前面：

Node* newNode = new Node(key, value);
newNode->next = buckets[index];
buckets[index] = newNode;

之所以用头插法，是因为实现简单，不需要遍历到链表尾部。

查找操作 get() 的逻辑与插入类似。它同样先通过哈希函数计算桶下标，然后只在该桶的链表中顺序比较：

bool get(int key, int& outValue) const {
    int index = hash(key);
    Node* cur = buckets[index];

    while (cur != nullptr) {
        if (cur->key == key) {
            outValue = cur->value;
            return true;
        }
        cur = cur->next;
    }

    return false;
}

这里最值得强调的一点是：哈希表查找并不是彻底不遍历，而是不再遍历整个表，而只遍历一个桶里的少量元素。
这正是它比普通数组按值查找、比链表线性扫描更快的根本原因。

此外，这里 get() 的第二个参数写成了 int& outValue。

2.4 运行结果

如果运行这段程序，大致会看到类似下面的输出：

当前哈希表内容：
bucket[0]:
bucket[1]: (17 -> 1700) (9 -> 900) (1 -> 100)
bucket[2]: (2 -> 200)
bucket[3]:
bucket[4]:
bucket[5]:
bucket[6]:
bucket[7]:
找到 key=9, value=900
没有找到 key=3
更新后 key=9, value=9999

这里最值得注意的是 bucket[1]。因为 1、9、17 都满足 % 8 == 1，所以它们发生了哈希冲突，被挂在同一个桶的链表上。由于这里采用的是头插法，后插入的元素会排在链表前面，因此打印顺序会是 (17 -> 1700) (9 -> 900) (1 -> 100)。

这个结果恰好非常直观地说明了三件事：第一，哈希冲突是会真实发生的；第二，拉链法确实能够容纳多个映射到同一桶的元素；第三，查找某个 key 时并不需要扫描整个表，而只需要进入对应桶并遍历其中的局部链表。

---

3. C++ 中的哈希库与常用操作

前一章手写了一个最小哈希表，其目的不是为了在实际开发中替代标准库，而是为了把哈希表的底层思想看明白。真正解决问题时通常不会自己从零实现一个哈希表，而是直接使用 C++ 标准库中已经封装好的哈希容器。

在 C++ 里，最常用的哈希容器主要有两个：unordered_map 和 unordered_set。从名字上就能看出来，它们都是“无序”的容器。这里的“无序”不是说数据乱了，而是说它们不保证按 key 的大小顺序存储元素。这和后面会提到的 map、set 有本质区别。

从功能上看，unordered_set 更像是一个“快速判存在”的集合，而 unordered_map 则是一个“快速建立映射关系”的表。前者只关心元素在不在，后者则关心 key 对应的 value 是什么。

3.1 unordered_set：只关心元素是否存在

先看 unordered_set。它本质上是一个哈希集合，集合里的每个元素只存一份，不允许重复。它最适合做的事情是：判断某个元素是否出现过、做去重、做判重。

一个最简单的例子如下：

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

int main() {
    unordered_set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(10);

    cout << s.size() << endl;

    if (s.count(10)) {
        cout << "10 存在" << endl;
    }

    if (!s.count(30)) {
        cout << "30 不存在" << endl;
    }

    s.erase(20);

    return 0;
}

这段代码里最核心的操作有三个：insert()、count() 和 erase()。
insert(x) 表示插入元素 x；count(x) 表示判断元素 x 是否存在；erase(x) 则表示删除元素 x。

这里有一个很重要的特性：由于 unordered_set 是集合，同一个元素不会被重复保存，所以连续插入两次 10，集合中也仍然只会有一个 10。这也是为什么它特别适合做判重。比如判断数组里是否存在重复元素，就非常适合使用 unordered_set。

例如：

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;

    for (int x : nums) {
        if (s.count(x)) {
            return true;
        }
        s.insert(x);
    }

    return false;
}

这个过程非常典型：一边遍历，一边把已经见过的元素放进哈希集合。如果某个元素在插入前已经存在，就说明它重复出现了。原本可能需要两层循环比较的事情，现在只需要一层循环加一次哈希查找，效率会高很多。

3.2 unordered_map：建立 key-value 映射

如果说 unordered_set 是“只存 key”，那么 unordered_map 就是“存 key-value 对”。它本质上是一个哈希映射表。

最简单的例子如下：

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

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

    mp[1] = 100;
    mp[2] = 200;
    mp[1] = 999;

    cout << mp[1] << endl;
    cout << mp[2] << endl;

    return 0;
}

这段代码说明了一个最基本的事实：unordered_map 中的每个 key 也是唯一的。当你写 mp[1] = 100 后，再写一次 mp[1] = 999，并不会新增一条记录，而是会把原来的值覆盖掉。

因此，unordered_map 特别适合做下面几类事情：

第一类是计数。例如统计每个数字出现了多少次。
第二类是建立映射关系。例如把“数值映射到下标”、“字符串映射到次数”、“字符映射到最后出现位置”等。
第三类是记录状态。例如记录某个前缀和出现过几次，或者某个节点是否访问过。

例如最常见的计数写法如下：

unordered_map<int, int> cnt;

for (int x : nums) {
    cnt[x]++;
}

这段代码很短，但它是哈希表题目里的核心模板之一。因为 cnt[x] 表示 key 为 x 对应的 value，而 ++ 则把出现次数加一。这个写法之所以方便，是因为当 x 这个 key 不存在时，unordered_map 会自动创建它，并给它一个默认值。对于 int 类型来说，默认值就是 0，所以第一次执行 cnt[x]++ 时，效果就相当于从 0 加到 1。

例如：

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

int main() {
    vector<int> nums = {1, 2, 1, 3, 2, 1};
    unordered_map<int, int> cnt;

    for (int x : nums) {
        cnt[x]++;
    }

    for (auto& p : cnt) {
        cout << p.first << " -> " << p.second << endl;
    }

    return 0;
}

这里 p.first 表示 key，p.second 表示 value。

3.3 常见操作：insert、count、find、erase、[]

先看 unordered_map。

1. 使用 [] 访问或赋值

unordered_map<int, int> mp;
mp[5] = 100;
cout << mp[5] << endl;

这里 mp[5] 的意思就是访问 key 为 5 的 value。如果 key 不存在，它会自动插入一个默认值再返回引用。

2. 使用 count() 判断 key 是否存在

if (mp.count(5)) {
    cout << "key 5 存在" << endl;
}

对 unordered_map 和 unordered_set 来说，count(x) 常常只会返回 0 或 1，因为 key 不允许重复。
所以在基础题里，它几乎就可以直接当布尔判断用。

3. 使用 find() 查找元素

auto it = mp.find(5);
if (it != mp.end()) {
    cout << it->second << endl;
}

find() 的返回值是一个迭代器。找到就返回对应位置，找不到就返回 end()。
这个写法比 count() 更灵活，因为找到以后可以直接拿到对应的 value。

对于 unordered_set，也可以用同样方式：

auto it = s.find(10);
if (it != s.end()) {
    cout << "找到了 10" << endl;
}

4. 使用 erase() 删除元素

mp.erase(5);
s.erase(10);

无论是 unordered_map 还是 unordered_set，erase() 都很直观，就是按 key 删除。

5. 使用范围 for 遍历

对于 unordered_map：

for (auto& p : mp) {
    cout << p.first << " -> " << p.second << endl;
}

对于 unordered_set：

for (int x : s) {
    cout << x << endl;
}

这里要注意，遍历 unordered_map 或 unordered_set 时，顺序是不确定的。不要以为输出顺序会和插入顺序一致，更不要指望它会自动按 key 排序。

3.4 unordered_map 和 map，unordered_set 和 set 的区别

这是 C++ 初学者最容易混淆的地方之一。

unordered_map 和 unordered_set 底层通常基于哈希表实现，特点是：

• 元素无序
• 查找、插入、删除平均复杂度通常是 O(1)

而 map 和 set 底层通常基于红黑树实现，特点是：

• 元素有序
• 查找、插入、删除复杂度通常是 O(log n)

所以这两类容器不是简单的“谁更高级”，而是侧重点不同。

如果你只是想快速判断元素在不在、快速做计数、快速做映射，那通常优先考虑 unordered_map 或 unordered_set。
如果需要按照 key 的大小顺序输出，或者后续操作需要“有序性”，那就应该考虑 map 或 set。

例如：

map<int, int> mp;
mp[3] = 30;
mp[1] = 10;
mp[2] = 20;

for (auto& p : mp) {
    cout << p.first << " -> " << p.second << endl;
}

这里输出会按 key 从小到大排列。而 unordered_map 则不保证这一点。

因此可以简单总结为：

• 关心快查找：优先 unordered_map / unordered_set
• 关心有序性：考虑 map / set

3.5 什么时候该想到哈希表

通常只要出现下面这些需求，就应该先往哈希表方向想：

• 判断某个元素是否出现过
• 判断数组中是否有重复值
• 统计每个元素出现的次数
• 记录某个值第一次或最后一次出现的位置
• 查找某个值的“补数”
• 建立值和位置、值和次数之间的映射关系

这些问题看似不同，但背后的本质很一致：**都需要在遍历过程中进行快速查找或快速记录。**而这正是哈希表最擅长的事情。

只要问题的关键在于“边遍历边快速查某个东西”，就很可能应该想到哈希表。

---

4. 实际例子

先看最经典的例子：两数之和。题目要求在数组中找出两个数，使它们的和等于目标值 target。暴力做法非常直接，就是两层循环枚举所有组合：

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

这种写法没有技术难点，但时间复杂度是 O(n^2)。一旦数组稍大，效率就会明显下降。

如果用哈希表，思路会完全不同。遍历到当前元素 nums[i] 时，我们不再回头去找另一个配对元素，而是直接问：我需要的那个数 target - nums[i] 之前有没有出现过？
如果之前出现过，那么答案立刻成立；如果之前没出现过，就把当前值和下标记下来，供后面的元素来查。

代码如下：

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;

    for (int i = 0; i < nums.size(); i++) {
        int need = target - nums[i];

        if (mp.count(need)) {
            return {mp[need], i};
        }

        mp[nums[i]] = i;
    }

    return {};
}

这个过程是把原本的“回头遍历查找”替换成了“哈希查找”。原来你为了找配对元素，要再跑一遍数组；现在只要查哈希表，平均情况下就能立刻知道它是否存在。所以整体时间复杂度从 O(n^2) 降到了 O(n)。

再看一个计数类问题。比如统计数组中每个元素出现的次数。如果用暴力思路去做，往往会写得很绕，因为必须想办法防止重复统计。哈希表在这里就非常自然，因为它天生适合做“值到次数”的映射：

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

int main() {
    vector<int> nums = {1, 2, 1, 3, 2, 1};

    unordered_map<int, int> cnt;
    for (int x : nums) {
        cnt[x]++;
    }

    for (auto& p : cnt) {
        cout << p.first << " 出现了 " << p.second << " 次" << endl;
    }

    return 0;
}

这里 p.first 是 key，p.second 是 value。也就是说，哈希表在这种场景下扮演的是“统计器”的角色。你不需要为每个值专门开变量，也不需要额外排序或手动去重，只要遍历一遍数据，哈希表就能把统计结果积累起来。

最后再做一个很实际的对比。什么时候应该用数组，什么时候应该用哈希表？如果数据范围非常小而且连续，例如统计 'a' 到 'z' 这 26 个小写字母的出现次数，那么直接开数组通常比哈希表更简单：

int cnt[26] = {0};
for (char c : s) {
    cnt[c - 'a']++;
}

这是因为数组下标天然可用，完全没必要多引入一层哈希映射。但如果 key 的范围很大，或者 key 根本不是整数下标，例如字符串、长整数、学号编号、坐标组合等，数组就不合适了。这种时候，哈希表的优势才真正体现出来。

所以，哈希表并不是“永远最优”。它最适合的场景是：需要快速判断某个值是否存在、需要统计频率、需要记录某个值第一次或最后一次出现的位置、或者需要建立某种 key-value 对应关系。