欢迎来到哈希表 (Hash Table) 的世界！
你有没有想过，电脑是如何在千万个数据中，于瞬间找到某一个特定使用者的资料？它绝对不会逐一搜索列表——那样太慢了！相反地，它使用一种称为哈希表 (Hash Table) 的精妙数据结构。
在本章中，我们将学习这些数据世界的“速度恶魔”是如何运作的。如果起初听起来有点像数学，别担心；一旦你掌握了当中的规律，它就像在编号的挂钩上找自己的外套一样简单！
1. 什么是哈希表？
哈希表是一种数据结构，它能在键 (Key)（例如用户名或 ID 编号）与值 (Value)（例如用户的个人资料）之间建立映射 (Mapping)。
你可以把它想象成健身房里的一大排置物柜。每个置物柜都有一个编号（称为索引 (Index) 或地址 (Address)）。你不需要搜索每个柜子来找你的包包，你有一个“神奇公式”，能根据你的名字直接告诉你属于你的柜子编号。
为什么要使用它？
我们使用哈希表的主要原因是速度。无论存储了多少数据，它们都能让我们几乎瞬间完成资料的寻找、新增或删除。
你知道吗？ 哈希表是数据库索引、缓存 (Cache)，甚至某些程序语言存储变量背后的秘密武器！
重点总结：
哈希表将键映射到内存中的特定位置，让我们可以瞬间找到它。
2. 神奇公式：哈希算法
我们如何决定一笔资料该放在哪里？我们使用哈希算法 (Hashing Algorithm)（或称哈希函数 (Hash Function)）。
哈希函数接收一个键作为输入，并将其转换为一个数字。这个数字会被用作存储资料的地址（数组中的索引）。
简单示例：模数法 (Modulo Method)
一种非常普遍且“简单”的哈希算法是模数 (Modulo) 法。
假设我们有一个包含 10 个槽位的哈希表（索引为 0 到 9）。我们的公式是：
\( \text{address} = \text{key} \pmod{\text{table\_size}} \)
如果我们的键是 124：
\( 124 \pmod{10} = 4 \)
所以，键 124 的资料会被存储在索引 4。
逐步解析：存储一个键
1. 取得键（例如 57）。
2. 运行哈希函数（例如 \( 57 \pmod{10} = 7 \)）。
3. 将资料存储在该索引（地址 7）。
如果觉得数学有点枯燥，别担心——只要记住函数只是一组规则，用来为资料挑选座位而已！
快速回顾：
哈希函数：将键转换为索引地址的计算过程。
3. 当空间拥挤时：冲突 (Collisions)
想象你在参加派对，主办人说：“每个人都坐在与你电话号码最后一位数字对应的椅子上。”如果你的号码尾数是 5，你就去 5 号椅。但如果别人的号码尾数也是 5 呢？
在计算机科学中，这称为冲突 (Collision)。
定义：当两个不同的键产生相同的哈希值（地址）时，就会发生冲突。
示例：使用我们的 \( \text{key} \pmod{10} \) 规则：
键 25 哈希后对应到索引 5。
键 85 哈希后也对应到索引 5。
糟糕！我们不能把两份资料放进同一个槽位。
重点总结：
在现实世界中，冲突是不可避免的，因为我们的可用键通常比表中的槽位多得多。
4. 解决问题：处理冲突
当冲突发生时，我们需要一个“备用方案”来为资料寻找新家。这通常称为再哈希 (Rehashing)。
线性探测 (Linear Probing)（“隔壁”法）
处理冲突最简单的方法就是寻找表中下一个可用的空槽位。
运作方式：
1. 计算地址（例如索引 5）。
2. 索引 5 满了吗？是的。
3. 查看索引 6。它是空的吗？如果是，把资料放进去！
4. 如果索引 6 也满了，就继续往 7、8 等后续位置移动。
搜索冲突资料
如果之后我们要寻找键 85，电脑会：
1. 将 85 进行哈希得到索引 5。
2. 检查索引 5。发现里面存的是键 25！（它知道这不是正确的资料）。
3. 它会接着检查后续的槽位（使用相同的冲突规则），直到找到 85 或一个空位为止。
要避免的常见错误：学生常认为哈希是“随机”的。其实不然！哈希函数必须是确定性 (Deterministic) 的——这意味着如果你输入相同的键，每次都必须得到相同的地址。
记忆小撇步：BUS 检查法
思考冲突时，想象一辆 BUS：
B (Busy) - 槽位是否忙碌 (Busy)？
U (Use) - 使用 (Use) 下一个槽位。
S (Search) - 搜索 (Search) 直到找到它为止！
快速回顾盒：
冲突：两个键，同一个地址。
再哈希：冲突发生时寻找新位置的过程（例如移至下一个空槽）。
章节总结
- 哈希表是将键映射到值的高速数据结构。
- 哈希函数计算存储资料的地址（索引）。
- 当两个键哈希到同一个地址时，会发生冲突。
- 再哈希（如线性探测）用于在冲突发生时找到替代的槽位。