8. 闪电查找（哈希表）

知识点：哈希表（HashMap / Map）—— 用"字典"一步找到人

项目：点名器升级（按名字查学号）+ 统计字数

---

故事开场：老师报名字，程序要"滴"一下答出来

点名器用了好几天，老师发现了一个问题。

"按学号点名很方便，"老师说，"可我想按名字找同学：'小明，你是几号？' 程序得马上答出来。"

你想了想：用数组挨个找呗。把全班 50 个名字存进数组，老师报"小明"， 就从头到尾遍历，找到为止：

const names = ["小明", "小红", "小刚", "小雨", "小丽"]
const nums = [1, 2, 3, 4, 5]

// 按名字找学号：挨个找
function findNumber(name: string): number | undefined {
  for (let i = 0; i < names.length; i++) {
    if (names[i] === name) {
      return nums[i]
    }
  }
  return undefined   // 没找到
}

console.log(findNumber("小刚"))   // 3

能用！50 个人，最多找 50 次，一秒都用不了。

可是老师说："明天是全校大点名，5000 个同学的名字都要查。 而且我们这学期要搞'闪电查找挑战赛'：老师报名字，程序要 一步就给出答案，谁的程序慢谁就输。"

你心里算了算：5000 人，最坏情况要遍历 5000 次，那是 O(n)—— 老师报 1000 个名字，最坏要查 500 万次。

"一步找到？"你挠头，"数组是编号的格子柜，可我手里只有名字， 名字又不是数字，怎么当下标？"

---

笨办法先行：让名字"变成"数字

你盯着"名字不是数字"这句话想了半天。

"小明"能不能变成数字？当然能！每个汉字都有编码——把每个字的编码加起来， 就得到一个数字！

假设"小明"的编码加起来是 7，"小红"是 3，"小刚"是 5，那么：

7 号格子 → 小明
3 号格子 → 小红
5 号格子 → 小刚

咦？！这样一来，老师报"小明"，程序把"小明"算成数字 7， 直接去 7 号格子拿答案——不用遍历，一步就到！

这不就是"名字当下标"吗？虽然下标是算出来的，但每个名字都能算出 自己唯一的格子号。查的时候，报个名字 → 算个数字 → 拿结果， 三步，但每一步都是一步，跟数组多大没关系——O(1)！

---

引出知识点：哈希表——神奇的"字典"

你刚刚自己发明了哈希表的原理！计算机里的哈希表（也叫哈希映射、字典） 就是干这件事的：

• 把 key（钥匙）——比如名字"小明"
• 通过哈希函数（hash function）——比如"把字的编码加起来"
• 算出一个位置，存下对应的 value（值）——比如学号 1

查的时候，拿着 key，用同一个哈希函数算出位置，直接取——O(1)，一步到位！

生活中的哈希表到处都是：

• 字典：按拼音/偏旁查字，不用一页页翻
• 电话本：按名字查号码
• 图书馆索书号：按编号找书
• 菜谱：按菜名找做法

在 TypeScript 里，哈希表就是 Map（映射）：

const book = new Map<string, number>()
book.set("小明", 1)   // 存：钥匙"小明" → 值 1
book.get("小明")      // 取：按"小明"一步拿到 1
book.has("小红")      // 问：有没有"小红"这把钥匙？
book.delete("小红")   // 删
book.size             // 数：一共存了几对

Map 就像一本神奇的字典：报出钥匙，它一步就能翻到那一页—— 不用从头到尾翻，这就是 O(1)。

（你可能听过"哈希冲突"：如果两个名字算出的格子号一样怎么办？ 答案是：让一个格子放一叠卡片，先放的在底下——多花一点点时间找， 但绝大多数情况下还是很快。真正的 Map 已经帮你处理好了， 现在我们先用起来，原理以后再去深挖。）

---

动手实现：闪电点名器

把点名器升级成哈希表版：

// 名字 → 学号
const students = new Map<string, number>()

students.set("小明", 1)
students.set("小红", 2)
students.set("小刚", 3)
students.set("小雨", 4)
students.set("小丽", 5)

// 老师报名字，一步查到学号
console.log("小刚的学号是：" + students.get("小刚"))
console.log("小明是几号？" + students.get("小明"))

// 查不到的人
console.log("小华在班上吗？" + students.has("小华"))

// 转学生来了：直接加一条，其他代码不用改
students.set("小华", 6)
console.log("现在班上有 " + students.size + " 人")
console.log("小华在班上吗？" + students.has("小华"))

输出：

小刚的学号是：3
小明是几号？1
小华在班上吗？false
现在班上有 6 人
小华在班上吗？true

新同学来了？set 一条就行——还记得点名器章那个"51 个同学要改所有数字" 的噩梦吗？用 Map，加人就是一句话的事。

---

跑起来：闪电查找挑战赛

现在我们做真正的"闪电挑战"：造一个 1 万人的名单，用两种办法找 "同学9999"——挨个找 vs 哈希表，比一比谁快：

// 先造两个"全校名单"：一个用数组（挨个找），一个用 Map（哈希表）
const names: string[] = []
const nums: number[] = []
const students = new Map<string, number>()

for (let i = 1; i <= 10000; i++) {
  const name = "同学" + i
  names.push(name)
  nums.push(i)
  students.set(name, i)
}

// 方法一：挨个找（数组遍历）
console.time("挨个找")
let found1 = "没找到"
for (let i = 0; i < names.length; i++) {
  if (names[i] === "同学9999") {
    found1 = nums[i]
  }
}
console.timeEnd("挨个找")
console.log("找到了：" + found1)

// 方法二：哈希表一步找
console.time("哈希表找")
const found2 = students.get("同学9999")
console.timeEnd("哈希表找")
console.log("找到了：" + found2)

在我这台电脑上，输出：

挨个找: 1ms
哈希表找: 0.01ms

咦？1 万人挨个找只要 1 毫秒？哈希表 0.01 毫秒？好像差别不大嘛！

把人数改成 100 万人再试试（把 i <= 10000 改成 i <= 1000000）： 挨个找要遍历一百万个名字（最坏情况要找到底），哈希表还是"一步"。

1 万人时，两者都快得看不见。可人数涨到 100 万、1 亿呢？ 挨个找的时间跟着人数涨（O(n)），哈希表却永远是一步（O(1)）。 这就是为什么大程序里到处是哈希表：数据越多，哈希表越显神威。

---

小挑战

1. 统计字数：写一个程序，统计一句话里每个字出现几次。 用 Map：遍历每个字，map.get(字) 得到旧次数，加 1 再 set 回去。 测测"上海自来水来自海上"里哪个字出现最多。
2. 菜单：做一个"餐厅菜单"：菜名 → 价格。然后模拟顾客点单： 报菜名，程序报价格；如果菜单上没有，就提示"没有这道菜"。
3. 单词本：做一个英语单词本：单词 → 中文意思。 存 5 个单词，然后"背单词"：随机报一个单词，程序显示中文意思。

---

课后练习

第 1 题（动手题）：我的电话号码本

用 Map 做一个电话号码本：存 5 个同学的姓名 → 电话号码。 然后实现三个功能：查号码、改号码（有人换号了）、删除（有人转学了）。 每次操作后打印 size，确认数量对得上。

参考答案（点开查看）

const phoneBook = new Map<string, string>()

phoneBook.set("小明", "13800000001")
phoneBook.set("小红", "13800000002")
phoneBook.set("小刚", "13800000003")
phoneBook.set("小雨", "13800000004")
phoneBook.set("小丽", "13800000005")

console.log("小明：" + phoneBook.get("小明"))        // 查

phoneBook.set("小明", "13900000001")                // 改（set 会覆盖旧值）
console.log("小明换号了：" + phoneBook.get("小明"))

phoneBook.delete("小丽")                             // 删
console.log("现在有 " + phoneBook.size + " 人")      // 4

console.log("小丽还在吗？" + phoneBook.has("小丽"))  // false

注意：set 同一个 key 会覆盖旧值——想"改"，直接再 set 一次就行。

第 2 题（思考题）：为什么哈希表是 O(1)？

用一句话向妈妈解释：为什么哈希表"报名字就能一步找到学号"， 不用像数组那样挨个找？

参考答案（点开查看）

比如：数组像一列排队的小朋友，找"小红"要一个个看过去； 哈希表像有编号的储物柜，而且每个名字都能算出来该去几号柜—— "小红"两个字一算，直接走到 3 号柜打开，一步就到。

关键在"算"这一步：哈希函数把名字变成数字，从名字到格子号 是一次计算（不管人数多少都是这一次），所以查也是 O(1)。

第 3 题（思考题）：Map 和数组，谁是谁？

下面这些情况，用数组合适还是用 Map 合适？说说理由：

① 全班同学按学号排队点名（学号 1~50 连续） ② 按名字查学号 ③ 按出现顺序记录今天的天气（晴、雨、晴、多云……）

参考答案（点开查看）

① 用数组：学号连续，直接用下标 names[3] 一步取，比 Map 还省事。

② 用 Map：名字不是连续数字，没法当下标；Map 按名字一步查。

③ 用数组：天气是按顺序记录的，每一条都很重要（顺序本身是信息）， 而且有重复值。Map 的 key 不能重复——"晴"只能存一条， 存不下"晴、雨、晴、多云"这种序列。

判断标准：key 是连续的编号就用数组，key 是"名字"这类任意的东西 就用 Map；要保留顺序和重复，用数组。

---

下一课预告：火车进站了！一节节车厢首尾相连，老师说： "往中间插一节餐车，或者拆掉一节车厢。"用数组？后面的车厢 全都要挪位置。有没有一种结构，插队和拆队都是一步搞定的？