查找算法：顺序查找、二分查找、哈希查找，哈希冲突解决
查找，说白了就是在一堆数据里找到你想要的那个。听起来简单，但实际写代码时，不同场景下的选择天差地别。我见过不少新手，上来就用顺序查找遍历几万条数据，结果程序卡得不行。也见过有人盲目用哈希表，结果内存爆了。
今天咱们就把三种主流查找算法掰开揉碎讲清楚。我会结合自己踩过的坑，告诉你什么时候该用哪个。
1. 顺序查找——最笨但最稳的方法
顺序查找的思路，就是从头到尾挨个比。数据量小的时候，这反而是最省心的方案。
// 顺序查找示例
int sequential_search(int *arr, int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // 找到了，返回下标
}
}
return -1; // 没找到
}时间复杂度是 O(n)，空间复杂度 O(1)。
适用场景：
- 数据量小（几十到几百条）
- 数据无序，且不打算排序
- 只需要查找一次，不值得建索引
2. 二分查找——前提是数据有序
二分查找的核心思想是「每次砍掉一半」。但有个硬性前提：数据必须是有序的。
// 二分查找（非递归版本）
int binary_search(int *arr, int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}时间复杂度 O(log n)，空间复杂度 O(1)。
适用场景：
- 数据量大且有序
- 查找操作频繁，但插入删除少
- 内存有限，不能建哈希表
3. 哈希查找——用空间换时间
哈希查找的思路是：通过一个哈希函数，直接把关键字映射到存储位置。理想情况下，查找时间是 O(1)。
// 简单的哈希查找（链地址法）
#define TABLE_SIZE 100
typedef struct Node {
int key;
int value;
struct Node *next;
} Node;
Node *hash_table[TABLE_SIZE];
int hash_func(int key) {
return key % TABLE_SIZE;
}
int hash_search(int key) {
int index = hash_func(key);
Node *cur = hash_table[index];
while (cur) {
if (cur->key == key) {
return cur->value;
}
cur = cur->next;
}
return -1; // 没找到
}平均时间复杂度 O(1)，最坏情况 O(n)。
4. 哈希冲突的解决——躲不开的问题
哈希冲突，说白了就是两个不同的key算出了同一个位置。我刚开始学的时候觉得这概率很小，直到自己写了一个简单的哈希表，数据量一上去，冲突就频繁出现。
常见的解决方法有四种：
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 链地址法 | 每个槽位挂一个链表 | 实现简单，删除方便 | 需要额外指针内存 |
| 开放地址法 | 冲突后找下一个空位 | 空间利用率高 | 删除麻烦，容易聚集 |
| 再哈希法 | 用另一个哈希函数 | 分布更均匀 | 计算开销大 |
| 公共溢出区 | 冲突数据放另一个表 | 结构清晰 | 溢出区可能成为瓶颈 |
我个人最常用的是链地址法。原因很简单：在嵌入式系统中，删除操作很常见，链地址法删除最方便。而且链表节点可以复用内存池，避免碎片化。
5. 三种查找算法的对比
| 算法 | 时间复杂度 | 空间复杂度 | 数据要求 | 适用场景 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无 | 小数据量，无序 |
| 二分查找 | O(log n) | O(1) | 有序 | 大数据量，静态数据 |
| 哈希查找 | O(1) 平均 | O(n) | 需哈希函数 | 高频查找，动态数据 |
6. 知识体系图
下面这张图帮你理清三种查找算法的核心逻辑和选择路径：
7. 实际项目中的选择策略
说了这么多理论，咱们聊聊实际项目中怎么选。我总结了一个简单的决策流程：
- 先看数据量：小于100条？顺序查找就够了，别折腾。
- 再看数据是否有序：如果数据本身有序，或者可以一次性排序，二分查找是性价比最高的选择。
- 最后看查找频率：如果查找非常频繁，而且数据动态变化（插入删除多），那就上哈希表。
我的一个真实案例： 之前做一个物联网网关项目，需要根据设备ID快速查找配置信息。设备数量大概5000个，查找频率很高，而且设备会动态上线离线。我一开始用了二分查找，每次插入都要重新排序，性能扛不住。后来改成哈希表（链地址法），查找时间从微秒级降到纳秒级，插入也变成了O(1)。
但代价是内存多了大概20KB。对于那个MCU来说，20KB换性能，值了。
嗯，这就是三种查找算法的核心内容。记住一点：没有最好的算法，只有最适合场景的算法。你想想看，顺序查找虽然慢，但代码简单、零依赖，在某些场景下反而是最稳的选择。