企业官网建设流程全解析

在前面的章节中，我们依次学习了数组、链表、栈、队列、递归、二分查找和排序算法。这些数据结构和算法帮我们解决了许多问题，但你有没有想过：有没有一种方法，能在"瞬间"找到某个数据？今天我们就来认识一种能让查找操作达到 O(1) 的神奇数据结构——哈希表（Hash Table）。

1. 什么是哈希表

想象一下你的手机通讯录。当你想找"张三"的电话号码时，你不会从第一个人开始逐个翻看，而是直接翻到"Z"开头的位置，瞬间找到目标。哈希表的原理与此类似。

哈希表的本质是一种"键 - 值"（Key-Value）映射结构。你给我一个"键"（比如名字），我通过某种计算，直接告诉你对应的"值"（比如电话号码）。这个过程不需要遍历，因此速度极快。

用更技术化的语言来说，哈希表通过一个"哈希函数"，将键映射到数组的某个下标，然后在该位置存储对应的值。这就是它能实现 O(1) 查找的秘密。

2. 哈希函数

哈希函数是哈希表的核心。它的作用是：把任意类型的"键"转换成一个数组下标（非负整数）。

最简单的方式是"取模运算"。假设我们的数组大小为 10，那么哈希函数可以是：

index = key % 10

举个例子：

通过这个简单的函数，我们把数字键直接映射到了数组的位置上。对于字符串类型的键，通常会先把每个字符的 ASCII 码加起来再取模，原理是一样的。

一个好的哈希函数应该尽量"均匀"地分布结果，避免太多键映射到同一个位置。

3. 哈希冲突

理想很美好，但现实总会遇到问题。如果两个不同的键经过哈希函数计算后得到了相同的下标，怎么办？这就是"哈希冲突"（Collision）。

例如，假设数组大小为 10：

23 % 10 = 3 33 % 10 = 3 ← 冲突了！

23 和 33 都映射到了下标 3，这就是冲突。哈希冲突是不可避免的（尤其是数据量大、数组小时），关键在于如何解决它。下面介绍两种最常见的方法。

3.1 链地址法

链地址法（Separate Chaining）的思路非常直观：数组的每个位置不直接存数据，而是挂一个"链表"。所有映射到同一位置的键值对，都放进这条链表里。

以上面的例子为例：

下标 3 → [23, 值A] → [33, 值B] → nullptr

查找时，先算出下标，再在对应链表中逐个比较键。如果链表很短，查找依然很快。

3.2 开放地址法

开放地址法（Open Addressing）不用链表，而是在冲突时"另找一个空位"存放。最简单的策略是"线性探测"（Linear Probing）：如果下标 i 被占了，就试 i+1、i+2、i+3……直到找到空位。

例如，23 先占据了下标 3，33 到来时发现下标 3 已满，于是放到下标 4。还有一种"二次探测"（Quadratic Probing），步长为 1²、2²、3²……，能减少数据聚集的问题。

4. C++ 中的哈希表：unordered_map

C++ 标准库为我们提供了现成的哈希表实现——unordered_map。下面是常用操作：

#include<iostream>#include<unordered_map>#include<string>usingnamespacestd;intmain(){unordered_map<string,int>phoneBook;// 插入phoneBook["张三"]=13800001111;phoneBook["李四"]=13900002222;phoneBook.insert({"王五",13700003333});// 查找autoit=phoneBook.find("李四");if(it!=phoneBook.end()){cout<<"李四的号码是："<<it->second<<endl;}// 使用 count 判断键是否存在if(phoneBook.