哈希表的原理与 C++ 数组模拟实现
导读：在海量数据中，如何实现近乎瞬时的查找？这就需要请出数据结构中的“极速跑车”——哈希表。本文将带你深刻理解哈希表的基础原理、哈希冲突的解决策略，并手撕 C++ 底层原生数组模拟哈希表（线性探测法与链地址法）的核心代码。
一、 什么是哈希表？
[cite_start]哈希表（Hash Table），在有些教材中也被称为散列表，它是一种能够根据关键字直接进行访问的高效数据结构 [cite: 1205, 1206]。
- [cite_start]核心机制：哈希表在内部建立了一种关键字和存储地址之间的直接映射关系，这使得每一个关键字都能与结构中的唯一存储位置相对应 [cite: 1207]。
- [cite_start]时间复杂度：在理想情况下，在散列表中进行查找的时间复杂度为 $O(1)$，也就是说，查询速度与表中的元素数量完全无关 [cite: 1207][cite_start]。因此，哈希表是一种存储和查找都极其迅速的结构 [cite: 1207]。
- [cite_start]哈希函数：建立这种映射关系的函数也叫作散列函数，通常记为 $Hash(key) = Addr$ [cite: 1208]。
二、 哈希冲突与常见映射策略
[cite_start]由于哈希表的空间是有限的，哈希函数可能会把两个或两个以上的不同关键字映射到同一个地址上，这种情况在计算机科学中被称为哈希冲突（或散列冲突） [cite: 1209][cite_start]。引起冲突的不同关键字，我们称它们互为“同义词” [cite: 1209]。
为了尽可能减少冲突，我们需要设计合理的哈希函数。常见的哈希函数有以下两种：
- [cite_start]直接定址法：直接取关键字的某个线性函数值作为哈希地址 [cite: 1211, 1212]。
- [cite_start]除留余数法：选取一个不太接近 2 的幂次方的质数，并且通过 key 除以这个数的余数，将其作为映射位置的下标 [cite: 1213, 1214]。
💡 实战避坑：负数取模的修正
[cite_start]在使用除留余数法时，我们需要考虑到传入的 key 值可能是一个负数 [cite: 1228][cite_start]。在 C++ 中，如果直接将负数相除取模，很可能会产生一个负数下标，从而导致数组越界 [cite: 1228]。
[cite_start]解决方案：使用模 + 模再取模的技巧即可完美解决 [cite: 1229][cite_start]。例如对于原始数字 $x$，无论是正数还是负数，使用(x % N + N) % N计算出的结果必定为正数的合法下标 [cite: 1230, 1231, 1232]。
三、 处理哈希冲突的核心方法与代码实现
面对不可避免的哈希冲突，业界主流有两种处理方案。在算法竞赛或底层开发中，我们通常使用原生数组来模拟这两种方案。
方法一：线性探测法 (开放寻址法)
[cite_start]原理：从发生冲突的位置开始，向后依次线性寻找没有存储数据的位置 [cite: 1216, 1217][cite_start]。如果一直寻找到哈希表的尾部还没有空位，就绕回到哈希表头部的位置继续寻找 [cite: 1217]。
核心经验：
- [cite_start]数组开大两倍：线性探测法在数据靠得非常近的时候，会发生“拥挤聚集”现象，大大增加搜索时的时间复杂度 [cite: 1222][cite_start]。解决方案是将数组开得更大一些 [cite: 1222][cite_start]。例如，如果元素总个数是 10，那么就将哈希表的数组大小开到两倍以上，并且在这个两倍数字附近寻找一个质数作为数组的最终大小 [cite: 1223]。
- [cite_start]无穷大初始化：由于我们直接在哈希表的数组中存放数据本身，如果提供的数据中恰好包含数字 0，那么默认初始化的 0 就会产生误判 [cite: 1224][cite_start]。因此，需要先将哈希表中的所有位置都初始化为一个不可能出现的数字，比如无穷大 [cite: 1224][cite_start]。在 C++ 中，通常使用常量
0x3f3f3f3f代表无穷大 [cite: 1225][cite_start]。借助memset(h, 0x3f, sizeof(h))可以快速完成初始化，因为每次设置一个字节，设置 4 个字节就正好拼接成了一个无穷大的整型值 [cite: 1226, 1227]。
C++ 模拟代码（已修复原笔记中的边界 Bug）：
#include<iostream>
#include<cstring>
using namespace std;// N 取数据量的两倍以上的质数
const int N = 23, INF = 0x3f3f3f3f; [cite_start]// [cite: 1237]
int h[N]; [cite_start]// [cite: 1238]// 初始化函数，将哈希表的每一个空位置都初始化为无穷大
[cite_start]void init() // [cite: 1240]
{memset(h, 0x3f, sizeof(h)); [cite_start]// [cite: 1242]
}// 设置哈希函数，返回 key 对应的位置或应该插入的空位置
[cite_start]int f(int x) // [cite: 1244, 1245]
{// x 是原始的 key，需要对其使用除留余数法进行转化int id = (x % N + N) % N; [cite_start]// [cite: 1247]// 修复 Bug：原笔记为 h[x]，现纠正为 h[id]// 逻辑：当前位置不为空，且当前位置的值不等于我们要找的值 x 时，继续向后找[cite_start]while (h[id] != INF && h[id] != x) { // [cite: 1248]id++; [cite_start]// [cite: 1249]// 同时需要注意是否越界，若到尾部则绕回头部if (id == N) id = 0; [cite_start]// [cite: 1251, 1252]}return id; [cite_start]// [cite: 1254]
}[cite_start]void insert(int d) // [cite: 1255]
{int id = f(d); [cite_start]// [cite: 1257]h[id] = d; [cite_start]// [cite: 1258]
}[cite_start]bool find(int d) // [cite: 1260]
{int id = f(d); [cite_start]// [cite: 1262]return h[id] == d; [cite_start]// [cite: 1263]
}[cite_start]int main() // [cite: 1265]
{init(); [cite_start]// [cite: 1267]return 0; [cite_start]// [cite: 1268]
}
方法二：链地址法 (拉链法)
[cite_start]原理：所有的数据本身不再直接存储在一维哈希表中，而是在哈希表中存储一个指向链表的指针 [cite: 1218, 1219][cite_start]。当有多个数据发生哈希冲突的时候，就在该位置的链表上挂上所有冲突的元素 [cite: 1219]。
C++ 模拟代码（单链表模拟实现）：
#include<iostream>
using namespace std;const int N = 23; [cite_start]// [cite: 1274]
int h[N]; [cite_start]// 充当链表头数组 [cite: 1275]
int ne[N], e[N]; [cite_start]// 链表节点的值和 next 指针 [cite: 1276]
int idx = 0; [cite_start]// 记录当前链表存储位置的移动指针 [cite: 1277, 1278][cite_start]int f(int x) // [cite: 1279]
{int id = (x % N + N) % N; [cite_start]// [cite: 1281]return id; [cite_start]// [cite: 1282]
}[cite_start]bool find(int d) // [cite: 1284]
{int id = f(d); [cite_start]// [cite: 1286]// 遍历对应哈希槽上的整条单链表[cite_start]for (int i = h[id]; i; i = ne[i]) // [cite: 1287]{[cite_start]if (e[i] == d) // [cite: 1289]{return true; [cite_start]// [cite: 1291]}}return false; [cite_start]// [cite: 1294]
}[cite_start]void insert(int d) // [cite: 1296]
{// 注意：以下方法使用的是链表头插法，无论是否已经存在都会插入。[cite_start]// 如果题目要求去重，所以需要加入 find() 存在性判断 [cite: 1300]if (find(d)) return; [cite_start]// [cite: 1298]int id = f(d); [cite_start]// [cite: 1301]e[++idx] = d; [cite_start]// 赋值新节点 [cite: 1302]ne[idx] = h[id]; [cite_start]// 新节点指向当前头结点 [cite: 1303]h[id] = idx; [cite_start]// 头结点更新为新节点 [cite: 1304]
}[cite_start]int main() // [cite: 1305]
{// ... 具体的输入输出测试逻辑return 0; [cite_start]// [cite: 1327]
}
声明：本博客由gemini基于laobie本地obsidian笔记转写，意在将obsidian内置图片转化为了纯文本或表格描述，便于博客上传