一、哈希表是什么？¶
想象一下，你在图书馆找一本书，管理员会告诉你这本书的“索书号”，你直接根据索书号就能定位到书架（类似“数组位置”），不需要一本本翻找。哈希表的作用和这完全一样：通过一个“钥匙”（哈希函数）快速找到数据的“位置”（数组索引），让查找、插入、删除操作变得非常高效。
简单来说，哈希表是一种键值对（key-value） 存储结构，它用一个“哈希函数”把“键”（比如学号、姓名）转换成数组的索引，然后把“值”（比如成绩、电话号码）存在对应的数组位置。
二、哈希表如何存储数据？¶
1. 哈希表的核心结构¶
哈希表的底层是一个数组，数组的每个位置称为“桶”（bucket）。每个桶可以存储一个值，当发生冲突时，可能会在桶里存多个值（取决于冲突解决方法）。
2. 存储步骤：钥匙→位置→存值¶
- 确定键值对：比如要存储学生信息：
学号=123，成绩=90。 - 计算哈希值：用“哈希函数”把键转换成数组索引。最简单的哈希函数是
哈希值 = 键 % 数组长度（比如数组长度为10，123 % 10 = 3，所以哈希值是3）。 - 存入数组：把“值”存在哈希值对应的数组位置（即第3个桶）。
示例：用哈希表存3个学生成绩¶
假设数组长度为10（桶编号0~9），哈希函数为 键 % 10：
- 学生A：学号12 → 哈希值 12%10=2 → 数组[2]存成绩85。
- 学生B：学号23 → 哈希值 23%10=3 → 数组[3]存成绩76。
- 学生C：学号34 → 哈希值 34%10=4 → 数组[4]存成绩92。
此时数组状态：[ , ,85,76,92, , , , , ]（空位置用逗号分隔）。
查询时，直接用学号计算哈希值（比如查学号12，哈希值2），直接访问数组[2]就能得到成绩85，无需遍历整个数组！
三、什么是冲突？¶
当两个不同的键通过哈希函数计算出相同的哈希值时，就会发生冲突。比如：
- 学号12和学号22，数组长度10，哈希函数%10：12%10=2，22%10=2。
此时，两个学生要存在数组[2]，但数组位置只有一个，就冲突了！
四、冲突解决方法（图解）¶
冲突是哈希表的“拦路虎”，但有两种经典方法解决：链地址法（拉链法） 和 开放定址法（线性探测）。
方法1：链地址法（拉链法）¶
原理：数组的每个桶是一个链表的“头节点”，冲突的元素直接挂在对应链表的尾部。
示例：继续存储学号22（成绩70），此时数组[2]已有85，发生冲突：
- 数组[2]变成链表：85 → 70（学生A的成绩挂在链表头，学生E的成绩挂在尾部）。
- 其他学生继续存入各自的哈希值对应的桶。
链地址法示意图（文字模拟）：
数组索引 → 桶 → 链表（冲突元素）
0 → []
1 → []
2 → [85] → [70] （学号12和22冲突，都存在链表中）
3 → [76] （学号23）
4 → [92] （学号34）
...
优点：实现简单，插入/删除方便，无聚集问题。
缺点：需要额外链表空间，适合初学者理解。
方法2：开放定址法（线性探测）¶
原理：冲突时，按顺序“探测”下一个空桶。线性探测的规则是：冲突位置h→h+1→h+2→…，直到找到空桶。
示例：数组长度10，存储学号12（85）和22（70）：
- 学号12：哈希值2 → 数组[2]为空，存85。
- 学号22：哈希值2 → 数组[2]被占，探测h+1=3（空），存70。
线性探测示意图（文字模拟表格）：
| 数组位置 | 0 | 1 | 2 | 3 | 4 | … |
|----------|—|—|—|—|—|-----|
| 状态 | | | 85 | 70 | 92 | … |
优点：无需额外数据结构，纯数组操作。
缺点：可能形成“聚集”（连续空桶被占用），影响效率。
五、总结¶
哈希表通过哈希函数将键映射到数组位置，实现了O(1)级别的快速操作。冲突不可避免，但通过链地址法（拉链法）或开放定址法（线性探测）可解决。
- 链地址法更直观，适合初学者，冲突元素用链表串联；
- 线性探测用数组自身空间解决冲突，简单但需注意聚集问题。
掌握哈希表的核心是理解“哈希函数→冲突→解决方法”的逻辑，这是后续学习更复杂数据结构的基础！